semidefinite programming bounds

Eigenvalue, Quadratic Programming, and Semidefinite Programming Relaxations for a Cut Minimization Problem

  • Ting Kei Pong
  • Henry Wolkowicz
  • Hao Sun
  • Ningchuan Wang
    • Categories Combinatorial Optimization, Graphs and Matroids, Semi-definite Programming Tags , , , ,

    We consider the problem of partitioning the node set of a graph into $k$ sets of given sizes in order to \emph{minimize the cut} obtained using (removing) the $k$-th set. If the resulting cut has value $0$, then we have obtained a vertex separator. This problem is closely related to the graph partitioning problem. In … Read more

    Optimality and uniqueness of the (4,10,1/6) spherical code

  • Christine Bachoc
  • Frank Vallentin
    • Categories Semi-definite Programming Tags , , , ,

    Traditionally, optimality and uniqueness of an (n,N,t) spherical code is proved using linear programming bounds. However, this approach does not apply to the parameter (4,10,1/6). We use semidefinite programming bounds instead to show that the Petersen code (which are the vertices of the 4-dimensional second hypersimplex or the midpoints of the edges of the regular … Read more