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 full item record

Title: Reduction of symmetric semidefinite programs using the regular representation.
Author: Klerk, Etienne de.; Pasechnik, Dmitrii V.; Schrijver, Alexander.
Copyright year: 2006
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.
Subject: DRNTU::Science::Mathematics.
Type: Journal Article
Series/ Journal Title: Mathematical programming
School: 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 ].
Version: Accepted version

Files in this item

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

DOI Query

- Get published version (via Digital Object Identifier)
   

This item appears in the following Collection(s)

Show full item record

Statistics

Total views

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

Total downloads

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

Top country downloads

Country Code Views
United States of America 50
Singapore 15
China 9
Japan 4
Iran 3

Top city downloads

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

Downloads / month

  2014-07 2014-08 2014-09 total
Reduction of symmetric semidefinite programs using the regular representation.pdf 0 0 2 2