theta bodies

A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs

  • João Gouveia
  • Monique Laurent
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite … Read more

    Theta Bodies for Polynomial Ideals

  • João Gouveia
  • Pablo A. Parrilo
  • Rekha R. Thomas
    • Categories Approximation Algorithms, Semi-definite Programming Tags , ,

    Inspired by a question of Lov\’asz, we introduce a hierarchy of nested semidefinite relaxations of the convex hull of real solutions to an arbitrary polynomial ideal, called theta bodies of the ideal. For the stable set problem in a graph, the first theta body in this hierarchy is exactly Lov{\’a}sz’s theta body of the graph. … Read more