19

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].

Community
  • 1
Snowie
  • 1,200
  • 7
  • 10
  • 1
    I would guess that geometric TSP would be an example of such a problem, but I do not have any references. – Jukka Suomela Feb 14 '11 at 19:06
  • 1
    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 Feb 14 '11 at 19:21
  • 1
    @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 Feb 14 '11 at 19:54
  • 1
    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 Feb 14 '11 at 19:59
  • 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? – Danu Feb 15 '11 at 00:02
  • @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 Feb 15 '11 at 00:15
  • @Danu: Any polynomial-size LP would be difficult to say. However, Mihalis Yannakakis showed that for matching no symmetric polynomial-sized LP exists, even though the problem is in P. – Kunal Feb 15 '11 at 20:01
  • 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 Feb 18 '11 at 22:49
  • @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 Oct 04 '13 at 14:45
  • (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 Apr 01 '15 at 21:12

3 Answers3

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.

Luca Trevisan
  • 4,912
  • 28
  • 34
8

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.

Kunal
  • 304
  • 1
  • 5
  • 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 Feb 15 '11 at 16:11
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.

YI WU
  • 61
  • 1