Reduction of symmetric semidefinite programs using the regular representation
We consider semidefinite programming problems on which a permutation group is acting.We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix ∗-representation of the commutant (centralizer ring) of the matrix algebra g...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/94065 http://hdl.handle.net/10220/7625 |
| _version_ | 1811688444495134720 |
|---|---|
| author | Klerk, Etienne de. Pasechnik, Dmitrii V. Schrijver, Alexander. |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Klerk, Etienne de. Pasechnik, Dmitrii V. Schrijver, Alexander. |
| author_sort | Klerk, Etienne de. |
| collection | NTU |
| description | We consider semidefinite programming problems on which a permutation group is acting.We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix ∗-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices.We apply it to extending amethod of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K8,n) ≥ 2.9299n2−6n, cr(K9,n) ≥ 3.8676n2 − 8n, and (for any m ≥ 9) lim n→∞ cr(Km,n)/Z(m, n) ≥ 0.8594 m/m − 1, where Z(m,n) is the Zarankiewicz number [1/4(m-1)2][1/4(n-1)2], which is the conjectured value of cr(K m,n ). Here the best factor previously known was 0.8303 instead of 0.8594. |
| first_indexed | 2024-10-01T05:32:18Z |
| format | Journal Article |
| id | ntu-10356/94065 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:32:18Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | ntu-10356/940652023-02-28T19:38:17Z Reduction of symmetric semidefinite programs using the regular representation Klerk, Etienne de. Pasechnik, Dmitrii V. Schrijver, Alexander. School of Physical and Mathematical Sciences DRNTU::Science::Mathematics We consider semidefinite programming problems on which a permutation group is acting.We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix ∗-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices.We apply it to extending amethod of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K8,n) ≥ 2.9299n2−6n, cr(K9,n) ≥ 3.8676n2 − 8n, and (for any m ≥ 9) lim n→∞ cr(Km,n)/Z(m, n) ≥ 0.8594 m/m − 1, where Z(m,n) is the Zarankiewicz number [1/4(m-1)2][1/4(n-1)2], which is the conjectured value of cr(K m,n ). Here the best factor previously known was 0.8303 instead of 0.8594. Accepted version 2012-03-09T00:44:11Z 2019-12-06T18:50:14Z 2012-03-09T00:44:11Z 2019-12-06T18:50:14Z 2006 2006 Journal Article Klerk, E. d., Pasechnik, D. V. & Schrijver, A. (2006). Reduction of symmetric semidefinite programs using the regular representation. Mathematical Programming, 109, 613-624. https://hdl.handle.net/10356/94065 http://hdl.handle.net/10220/7625 10.1007/s10107-006-0039-7 en Mathematical programming © 2006 Springer-Verlag. This is the author created version of a work that has been peer reviewed and accepted for publication by Mathematical Programming, Springer-Verlag. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [DOI: http://dx.doi.org/10.1007/s10107-006-0039-7 ]. 11 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics Klerk, Etienne de. Pasechnik, Dmitrii V. Schrijver, Alexander. Reduction of symmetric semidefinite programs using the regular representation |
| title | Reduction of symmetric semidefinite programs using the regular representation |
| title_full | Reduction of symmetric semidefinite programs using the regular representation |
| title_fullStr | Reduction of symmetric semidefinite programs using the regular representation |
| title_full_unstemmed | Reduction of symmetric semidefinite programs using the regular representation |
| title_short | Reduction of symmetric semidefinite programs using the regular representation |
| title_sort | reduction of symmetric semidefinite programs using the regular representation |
| topic | DRNTU::Science::Mathematics |
| url | https://hdl.handle.net/10356/94065 http://hdl.handle.net/10220/7625 |
| work_keys_str_mv | AT klerketiennede reductionofsymmetricsemidefiniteprogramsusingtheregularrepresentation AT pasechnikdmitriiv reductionofsymmetricsemidefiniteprogramsusingtheregularrepresentation AT schrijveralexander reductionofsymmetricsemidefiniteprogramsusingtheregularrepresentation |