Reduction of symmetric semidefinite programs using the regular *-representation

Etienne De Klerk (E.deKlerkuvt.nl)
Dmitrii V. Pasechnik (D.V.Pasechnikuvt.nl)
Alexander Schrijver (Lex.Schrijvercwi.nl)

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 a method of de Klerk et al. that gives a semidefinite programming lower bound to the crossing number of complete bipartite graphs.

Keywords: Semidefinite programming, regular *-representation, crossing number, complete bipartite graphs

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: Preprint, February, 2005.

Download: [PDF]

Entry Submitted: 03/03/2005
Entry Accepted: 03/03/2005
Entry Last Modified: 03/03/2005

Modify/Update this entry