crossing number

EXPLOITING SYMMETRY IN COPOSITIVE PROGRAMS VIA SEMIDEFINITE HIERARCHIES

  • Cristian Dobre
  • Juan C. Vera
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    Copositive programming is a relative young field which has evolved into a highly active research area in mathematical optimization. An important line of research is to use semidefinite programming to approximate conic programming over the copositive cone. Two major drawbacks of this approach are the rapid growth in size of the resulting semidefinite programs, and … Read more

    Reduction of symmetric semidefinite programs using the regular *-representation

  • Etienne de Klerk
  • Dmitrii V. Pasechnik
  • Alexander Schrijver
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    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 … Read more