mirage

Reduction of symmetric semidefinite programs using the regular representation.

DSpace/Manakin Repository

 

Search DR-NTU


Advanced Search Subject Search

Browse

My Account

Reduction of symmetric semidefinite programs using the regular representation.

Show simple item record

dc.contributor.author Klerk, Etienne de.
dc.contributor.author Pasechnik, Dmitrii V.
dc.contributor.author Schrijver, Alexander.
dc.date.accessioned 2012-03-09T00:44:11Z
dc.date.available 2012-03-09T00:44:11Z
dc.date.copyright 2006
dc.date.issued 2012-03-09
dc.identifier.citation Klerk, E. d., Pasechnik, D. V. & Schrijver, A. (2006). Reduction of symmetric semidefinite programs using the regular representation. Mathematical Programming, 109, 613-624.
dc.identifier.uri http://hdl.handle.net/10220/7625
dc.description.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.
dc.format.extent 11 p.
dc.language.iso en
dc.relation.ispartofseries Mathematical programming
dc.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 ].
dc.subject DRNTU::Science::Mathematics.
dc.title Reduction of symmetric semidefinite programs using the regular representation.
dc.type Journal Article
dc.contributor.school School of Physical and Mathematical Sciences
dc.identifier.doi http://dx.doi.org/10.1007/s10107-006-0039-7
dc.description.version Accepted version

Files in this item

Files Size Format View
Reduction of sy ... regular representation.pdf 155.4Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Statistics

Total views

All Items Views
Reduction of symmetric semidefinite programs using the regular representation. 166

Total downloads

All Bitstreams Views
Reduction of symmetric semidefinite programs using the regular representation.pdf 90

Top country downloads

Country Code Views
United States of America 42
Singapore 15
China 8
Japan 4
Iran 3

Top city downloads

city Views
Mountain View 35
Singapore 15
Semnan 3
Montreal 2
Southampton 2

Downloads / month

  2014-05 2014-06 2014-07 total
Reduction of symmetric semidefinite programs using the regular representation.pdf 0 0 5 5