lovasz theta function

A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags , ,

    Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming Strong Duality into combinatorial min-max theorems. The definition of total dual integrality (TDI) revolves around the existence of optimal dual solutions that are integral, and thus naturally applies … Read more

    On the Lovasz Theta Function and Some Variants

  • Laura Galli
  • Adam N. Letchford
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

    The Lovasz theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovasz and the other to Groetschel et al. The former SDP is often thought to be preferable … Read more