18
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ I would guess that geometric TSP would be an example of such a problem, but I do not have any references. $\endgroup$ – Jukka Suomela Feb 14 '11 at 19:06
  • 1
    $\begingroup$ 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? $\endgroup$ – Jukka Suomela Feb 14 '11 at 19:21
  • 1
    $\begingroup$ @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 $\endgroup$ – Luca Trevisan Feb 14 '11 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Luca Trevisan Feb 14 '11 at 19:59
  • $\begingroup$ 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? $\endgroup$ – Danu Feb 15 '11 at 0:02
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Snowie Feb 15 '11 at 16:11
8
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.