Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/94065
Title: | Reduction of symmetric semidefinite programs using the regular representation | Authors: | Klerk, Etienne de. Pasechnik, Dmitrii V. Schrijver, Alexander. |
Keywords: | DRNTU::Science::Mathematics | Issue Date: | 2006 | Source: | Klerk, E. d., Pasechnik, D. V. & Schrijver, A. (2006). Reduction of symmetric semidefinite programs using the regular representation. Mathematical Programming, 109, 613-624. | Series/Report no.: | Mathematical programming | Abstract: | 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. | URI: | https://hdl.handle.net/10356/94065 http://hdl.handle.net/10220/7625 |
DOI: | 10.1007/s10107-006-0039-7 | Schools: | School of Physical and Mathematical Sciences | Rights: | © 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 ]. | Fulltext Permission: | open | Fulltext Availability: | With Fulltext |
Appears in Collections: | SPMS Journal Articles |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Reduction of symmetric semidefinite programs using the regular representation.pdf | 151.8 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
5
81
Updated on Mar 19, 2024
Web of ScienceTM
Citations
5
66
Updated on Oct 25, 2023
Page view(s) 50
608
Updated on Mar 28, 2024
Download(s) 10
389
Updated on Mar 28, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.