Reduction of symmetric semidefinite programs using the regular *-representation
Etienne De Klerk (E.deKlerkuvt.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.
Entry Submitted: 03/03/2005
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|