3

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.

arnab
  • 7,000
  • 1
  • 38
  • 55
  • 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. – caozhu Apr 01 '15 at 12:24
  • @caozhu: Yes, linear programming is P-complete, but I was asking for a "natural" LP relaxation with an integrality gap. – arnab Apr 01 '15 at 12:38
  • 2
    Just found this previous question (http://cstheory.stackexchange.com/questions/4915/integrality-gap-and-approximation-ratio) though there the question didn't ask for problems in P. But Yi Wu's answer there (http://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? – arnab Apr 01 '15 at 12:46
  • 2
    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. – Sasho Nikolov Apr 01 '15 at 18:52
  • 2
    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. – Neal Young Apr 01 '15 at 21:12
  • 1
    Not your question, but... Independent set of segments, has integrality gap $n/2$, but there is a QPTAS. – Sariel Har-Peled Apr 02 '15 at 03:14

0 Answers0