vertex separator problem

Facial Reduction for Symmetry Reduced Semidefinite Programs

  • Hao Hu
  • Renata Sotirov
  • Henry Wolkowicz
    • Categories Semi-definite Programming Tags , , , ,

    We consider both facial and symmetry reduction techniques for semidefinite programming, SDP. We show that the two together fit surprisingly well in an alternating direction method of multipliers, ADMM, approach. The combination of facial and symmetry reduction leads to a significant improvement in both numerical stability and running time for both the ADMM and interior … Read more

    A copositive programming approach to graph partitioning

  • Janez Povh
  • Franz Rendl
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that … Read more