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

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

CC BY-SA 3.0
2015-04-01T12:24:37.763Z
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
CC BY-SA 3.0
2015-04-01T12:38:04.247Z
@caozhu: Yes, linear programming is P-complete, but I was asking for a "natural" LP relaxation with an integrality gap.
arnab
CC BY-SA 3.0
2015-04-01T12:46:27.493Z
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
CC BY-SA 3.0
2015-04-01T18:52:00.203Z
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
CC BY-SA 3.0
2015-04-01T21:12:11.923Z
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
CC BY-SA 3.0
2015-04-02T03:14:37.327Z
Not your question, but... Independent set of segments, has integrality gap $n/2$, but there is a QPTAS.
Sariel Har-Peled
<ds.algorithms><approximation-algorithms><linear-programming><integrality-gap>
Exactly solvable but non-trivial integrality gap
arnab
# Exactly solvable but non-trivial integrality gap

(Asked by: username_0 on 2015-04-01)

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.

**Tags:** ds.algorithms, approximation-algorithms, linear-programming, integrality-gap

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1: Yes, linear programming is P-complete, but I was asking for a "natural" LP relaxation with an integrality gap.  
> **username_0**: 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?  
> **username_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.  
> **username_3**: 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.  
> **username_4**: Not your question, but... Independent set of segments, has integrality gap $n/2$, but there is a QPTAS.  

---

## 0 answers

