Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap?

Note: Maximum matching doesn't qualify because I consider natural the exponential-sized poly-time solvable LP.

  • $\begingroup$ I'm afraid the answer would probably be no. Any familiar problems with non-trivial integrality gap are NP, such as vertex cover. In fact, for polynomial time solvable problems, one can manually construct an LP that gives the answer while having no integrality gaps. $\endgroup$ – caozhu Apr 1 '15 at 12:24
  • 2
    $\begingroup$ Just found this previous question (cstheory.stackexchange.com/questions/4915/…) though there the question didn't ask for problems in P. But Yi Wu's answer there (cstheory.stackexchange.com/a/4926/15) about Schoenebeck's result on solving a system of linear equations works. Maybe one of the moderators could turn this into a community wiki? $\endgroup$ – arnab Apr 1 '15 at 12:46
  • 2
    $\begingroup$ I think it's ok to answer your own question, with a link to the other answer. By the way I am surprised you consider the matching polytope constraints natural. If I was seeing the matching problem for the first time, it would take me some time before I decide to throw in odd set constraints. $\endgroup$ – Sasho Nikolov Apr 1 '15 at 18:52
  • 2
    $\begingroup$ One "natural" LP for minimum spanning tree comes to mind. The LP is to assign a value in [0,1] to each edge, so that the total value crossing each cut is at least 1. The objective is to minimize the sum of the edge values, weighted by edge costs. There are exponentially many constraints, but there exists a separation oracle (min cut). The integrality gap is (at least?) two --- e.g. in a complete graph with unit edge weights, give the edges on a Hamiltonian cycle each value 1/2. $\endgroup$ – Neal Young Apr 1 '15 at 21:12
  • 1
    $\begingroup$ Not your question, but... Independent set of segments, has integrality gap $n/2$, but there is a QPTAS. $\endgroup$ – Sariel Har-Peled Apr 2 '15 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.