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...
Saved in:
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | Article |
| 語言: | English |
| 出版: |
2012
|
| 主題: | |
| 在線閱讀: | https://hdl.handle.net/10356/94065 http://hdl.handle.net/10220/7625 |
| 標簽: |
添加標簽
沒有標簽, 成為第一個標記此記錄!
|
| 機構: | Nanyang Technological University |
| 語言: | English |
| 總結: | 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. |
|---|