Reduction of symmetric semidefinite programs using the regular *-representation

• 成果类型: Article
• 署名作者: de Klerk, Etienne; Pasechnik, Dmitrii V.; Schrijver, Alexander
• 署名单位: Centrum Wiskunde & Informatica (CWI); University of Amsterdam; Tilburg University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0039-7
• 发表日期: 2007
• 页码: 613-624
• 关键词: Bounds

摘要

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 a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs. It implies that cr(K-8,K-n ) >= 2.9299n(2)-6n, cr(K-9,K-n ) >= 3.8676n(2)-8n, and (for any m >= 9) [GRAPHICS] 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.