<p>There are various examples in which a semidefinite programming relaxation allows an approximation that is superior to known integrality gaps for linear programming relaxations.</p>

<p>For example, the standard linear programming relaxation of max cut has an integrality gap of 1/2, and this is true even for much more sophisticated linear programming relaxations (c.f. de la Vega-Kenyon and Schoenebeck-Trevisan-Tulsiani), but the Goemans-Williamson SDP algorithm has approximation .878...</p>

<p>The Leighton-Rao linear programming relaxation of sparsest cut has an integrality gap $\Omega(\log n)$, but the Arora-Rao-Vazirani SDP algorithm has approximation $O(\sqrt{\log n})$.</p>

<p>Perhaps less well known, Karloff and Zwick shows that using SDP one can approximate Max 3SAT, in the version in which clauses can have 1, 2 or 3 literals, within 7/8, while Goemans and Williamson had studied a linear programming relaxation that they used to prove a 3/4 approximation (Yannakakis had given 3/4 approximation earlier by other methods), and the Goemans-Williamson LP relaxation of Max 3SAT is easily seen to have integrality gap 3/4.</p>

CC BY-SA 2.5
2011-02-14T18:26:56.140Z
2011-02-14T18:26:56.140Z
Luca Trevisan
<p>There is also a result by Grant on solving linear systems over GF_2. For equation systems with a good solution, you have a SDP integrality gap (in a very strong form) of 2 while you can use Gaussian Elimination to solve the problem exactly. </p>

CC BY-SA 2.5
2011-02-14T22:30:30.190Z
2011-02-14T22:30:30.190Z
YI WU
<p>As pointed out, there are quite a few examples.</p>

<p>A classical example is maximum matching, where the "natural" relaxation (without odd set constraints) has a gap of 2, while there is of course an efficient algorithm. This one does not fully qualify though, since there is an exponential sized LP which can be solved via ellipsoid.</p>

<p>An intriguing one is capacitated facility location. Here the natural relaxation has unbounded integrality gap. Yet local search based algorithms give constant factor approximations.</p>

<p>Another very interesting one (though it's a maximization problem) is this paper: <a href="http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf">http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf</a>. Here the LP has a large gap, and yet an algorithm that uses that LP can do better.</p>

CC BY-SA 2.5
2011-02-15T16:11:23.310Z
Thank you very much.  This answer contains what I was looking for, especially the FOCS paper written by Chakrabarty et al. (this paper interests me so much).  Therefore I set this answer as accepted.  I am still looking for more examples though and so anyone who can give other examples would be highly appreciated.
Snowie
CC BY-SA 2.5
2011-02-14T22:47:18.733Z
2011-02-14T22:47:18.733Z
Kunal
<p>When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of algorithms (such as rounding or primal-dual algorithm).  In fact, there are many problems whose best approximation ratio matches the integrality gap.</p>

<p>Some algorithm may have a better approximation ratio than the integrality gap for some problem, but I don't know if such an example exists or not.  If the answer is yes, could you give some examples?</p>

<p>I know that some problems admit multiple mathematical formulations.  In such cases, consider the mathematical formulation with the smallest integrality gap, as long as it can be solved in polynomial time (perhaps some formulations may use separation oracles).</p>

<p>This question is related to <a href="https://cstheory.stackexchange.com/questions/392/the-importance-of-integrality-gap">[the question: The importance of Integrality Gap]</a>.</p>

CC BY-SA 3.0
2013-10-04T14:45:17.723Z
@Danu extension complexity deals with this type of results, once you fix the mapping from the combinatorial problem to real vectors (which goes around Jukka's obstruction)
Sasho Nikolov
CC BY-SA 3.0
2015-04-01T21:12:41.643Z
(i) Dantzig et al's natural LP for the NP-hard min-weight triangulation problem (exact covering by triangles) has unbounded integrality gap for general cost vectors, but constant integrality gap for the cost vector that comes from Euclidean distances.  (ii) Another "natural" example is an LP for MST (see http://cstheory.stackexchange.com/questions/30984/exactly-solvable-but-non-trivial-integrality-gap).
Neal Young
CC BY-SA 2.5
2011-02-14T19:06:02.520Z
I would guess that geometric TSP would be an example of such a problem, but I do not have any references.
Jukka Suomela
CC BY-SA 2.5
2011-02-14T19:21:37.077Z
And what about problems that admit a PTAS using the shifting strategy? Does any of those have an IP formulation with an arbitrarily small integrality gap?
Jukka Suomela
CC BY-SA 2.5
2011-02-14T19:54:11.633Z
@Jukka geometric TSP is a good example. The 4/3 integrality gap example is a shortest-path metric on a planar graph, and it should be possible to turn into an instance of Euclidean TSP or $\ell_1$ TSP in the plane with a $1+\epsilon$ gap
Luca Trevisan
CC BY-SA 2.5
2011-02-14T19:59:00.180Z
I heard it mentioned as an interesting open question whether PTASs for problems on planar graphs can be realized by using a constant number of levels of Sherali-Adams or Lasserre relaxations. (Where the constant depends on the approximation ration that one wants to achieve.) It should be known, or at least provable with current techniques, that the graph problems that have PTASs in dense graphs (e.g. max cut) also have a family of polynomial size relaxations with arbitrarily small integrality gaps.
Luca Trevisan
CC BY-SA 2.5
2011-02-15T00:02:07.337Z
Related question: Is there any problem that is proved that any polynomial-size LP cannot give the current best known approximation ratio? Is it possible to prove such thing, even for some restricted types of LPs?
Dan
CC BY-SA 2.5
2011-02-15T00:15:05.540Z
@Danu: Note that linear programming is a P-complete problem. I think this makes it very difficult to come up with a reasonable formulation that would permit "typical" LP relaxations but not allow us to simulate any polynomial-time algorithm... Hence I guess the question is inherently somewhat subjective?
Jukka Suomela
CC BY-SA 2.5
2011-02-15T20:01:22.110Z
@Danu: _Any_ polynomial-size LP would be difficult to say. However, Mihalis Yannakakis [showed](http://dx.doi.org/10.1016/0022-0000(91)90024-Y) that for matching no symmetric polynomial-sized LP exists, even though the problem is in P.
Kunal
CC BY-SA 2.5
2011-02-18T22:49:22.943Z
The paper of Magen and Moharrami is related to the comment of Luca above. It shows that for max independent set and min vertex cover one can get PTASes in planar and minor-free graphs by using Sherali-Adams hierarchy. http://www.cs.toronto.edu/~avner/papers/SA-planar.pdf
Chandra Chekuri
<ds.algorithms><approximation-algorithms><linear-programming><integrality-gap>
Integrality gap and approximation ratio
Snowie
# Integrality gap and approximation ratio

(Asked by: username_0 on 2011-02-14)

When we consider an approximation algorithm for a minimization problem, the integrality gap of an IP formulation for this problem gives a lower bound of an approximation ratio for certain class of algorithms (such as rounding or primal-dual algorithm). In fact, there are many problems whose best approximation ratio matches the integrality gap.

Some algorithm may have a better approximation ratio than the integrality gap for some problem, but I don't know if such an example exists or not. If the answer is yes, could you give some examples?

I know that some problems admit multiple mathematical formulations. In such cases, consider the mathematical formulation with the smallest integrality gap, as long as it can be solved in polynomial time (perhaps some formulations may use separation oracles).

This question is related to [[the question: The importance of Integrality Gap]](https://cstheory.stackexchange.com/questions/392/the-importance-of-integrality-gap).

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

> **Comments:**
> **username_3**: I would guess that geometric TSP would be an example of such a problem, but I do not have any references.  
> **username_3**: And what about problems that admit a PTAS using the shifting strategy? Does any of those have an IP formulation with an arbitrarily small integrality gap?  
> **username_4**: @Jukka geometric TSP is a good example. The 4/3 integrality gap example is a shortest-path metric on a planar graph, and it should be possible to turn into an instance of Euclidean TSP or $\ell_1$ TSP in the plane with a $1+\epsilon$ gap  
> **username_4**: I heard it mentioned as an interesting open question whether PTASs for problems on planar graphs can be realized by using a constant number of levels of Sherali-Adams or Lasserre relaxations. (Where the constant depends on the approximation ration that one wants to achieve.) It should be known, or at least provable with current techniques, that the graph problems that have PTASs in dense graphs (e.g. max cut) also have a family of polynomial size relaxations with arbitrarily small integrality gaps.  
> **username_5**: Related question: Is there any problem that is proved that any polynomial-size LP cannot give the current best known approximation ratio? Is it possible to prove such thing, even for some restricted types of LPs?  
> **username_3**: @username_5u: Note that linear programming is a P-complete problem. I think this makes it very difficult to come up with a reasonable formulation that would permit "typical" LP relaxations but not allow us to simulate any polynomial-time algorithm... Hence I guess the question is inherently somewhat subjective?  
> **username_6**: @username_5u: _Any_ polynomial-size LP would be difficult to say. However, Mihalis Yannakakis [showed](http://dx.doi.org/10.1016/0022-0000(91)90024-Y) that for matching no symmetric polynomial-sized LP exists, even though the problem is in P.  
> **username_7**: The paper of Magen and Moharrami is related to the comment of Luca above. It shows that for max independent set and min vertex cover one can get PTASes in planar and minor-free graphs by using Sherali-Adams hierarchy. http://www.cs.toronto.edu/~avner/papers/SA-planar.pdf  
> **username_1**: @username_5u extension complexity deals with this type of results, once you fix the mapping from the combinatorial problem to real vectors (which goes around Jukka's obstruction)  
> **username_2**: (i) username_5tzig et al's natural LP for the NP-hard min-weight triangulation problem (exact covering by triangles) has unbounded integrality gap for general cost vectors, but constant integrality gap for the cost vector that comes from Euclidean distances.  (ii) Another "natural" example is an LP for MST (see http://cstheory.stackexchange.com/questions/30984/exactly-solvable-but-non-trivial-integrality-gap).  

---

## 3 answers

### Answer by username_6 on 2011-02-14. Score: 8 | Accepted answer

As pointed out, there are quite a few examples.

A classical example is maximum matching, where the "natural" relaxation (without odd set constraints) has a gap of 2, while there is of course an efficient algorithm. This one does not fully qualify though, since there is an exponential sized LP which can be solved via ellipsoid.

An intriguing one is capacitated facility location. Here the natural relaxation has unbounded integrality gap. Yet local search based algorithms give constant factor approximations.

Another very interesting one (though it's a maximization problem) is this paper: <http://www.cis.upenn.edu/~sanjeev/postscript/FOCS09_MaxMin.pdf>. Here the LP has a large gap, and yet an algorithm that uses that LP can do better.

> **Comments:**
> **username_0**: Thank you very much.  This answer contains what I was looking for, especially the FOCS paper written by Chakrabarty et al. (this paper interests me so much).  Therefore I set this answer as accepted.  I am still looking for more examples though and so anyone who can give other examples would be highly appreciated.  

---

### Answer by username_4 on 2011-02-14. Score: 8

There are various examples in which a semidefinite programming relaxation allows an approximation that is superior to known integrality gaps for linear programming relaxations.

For example, the standard linear programming relaxation of max cut has an integrality gap of 1/2, and this is true even for much more sophisticated linear programming relaxations (c.f. de la Vega-Kenyon and Schoenebeck-Trevisan-Tulsiani), but the Goemans-Williamson SDP algorithm has approximation .878...

The Leighton-Rao linear programming relaxation of sparsest cut has an integrality gap $\Omega(\log n)$, but the Arora-Rao-Vazirani SDP algorithm has approximation $O(\sqrt{\log n})$.

Perhaps less well known, Karloff and Zwick shows that using SDP one can approximate Max 3SAT, in the version in which clauses can have 1, 2 or 3 literals, within 7/8, while Goemans and Williamson had studied a linear programming relaxation that they used to prove a 3/4 approximation (Yannakakis had given 3/4 approximation earlier by other methods), and the Goemans-Williamson LP relaxation of Max 3SAT is easily seen to have integrality gap 3/4.


---

### Answer by username_8 on 2011-02-14. Score: 6

There is also a result by Grant on solving linear systems over GF\_2. For equation systems with a good solution, you have a SDP integrality gap (in a very strong form) of 2 while you can use Gaussian Elimination to solve the problem exactly.


---

