The importance of Integrality Gap

Question

I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real solution of the relaxation of the problem. Lets consider vertex cover (VC) as an example. VC can be stated as finding an optimal integer solution of the following set of linear equations:

We have zero/one valued variables $x_v$s for each vertex $v \in V(G)$ of the graph $G$. The equations are: $0 \leq x_v \leq 1$ for $v\in V(G)$, and $1 \leq x_v+x_u$ for each edge $uv \in E(G)$. We are looking for values which will minimize $\sum_{v \in V(G)} x_v$.

The relaxation of this problem allows real values between $0$ and $1$ so the space of solutions is larger and an optimal real solution can be smaller than an optimal integer solution we want to find. Therefore we need to perform a "rounding" process on the optimal real answer obtained from linear programming to find an integer solution. The optimal integer solution will be between the optimal real solution and the result of the rounding process. IG is the ratio of an optimal integer solution to an optimal real solution and does not say anything about the rounding process. The rounding process can (in theory) completely ignore the real solution and compute the optimal integer solution directly.

Why are people interested in proving bounds on IG?

Answer 1

Integrality gaps essentially represent the inherent limits of a particular linear or convex relaxation in approximating an integer program. Generally, if the integrality gap of a particular relaxation is $x$, then any approximation algorithm based on that relaxation cannot hope to do better than an $x$-approximation. So at the very least, integrality gaps are of interest to algorithm designers since they suggest limitations in certain techniques.

So why not just come up with another LP relaxation or switch to other techniques and move on? Linear and convex programming have proven to be central to approximation algorithms; for many problems the integrality gap of a natural LP or SDP formulation is equal to the approximation ratio of the best algorithm as well as the hardness of approximation ratio. This is just an empirical observation, but it means that proving an integrality gap may suggest much stronger consequences of an improved algorithm or lower bound.

There may be deeper and more rigorous reasons for this phenomenon. For instance, assuming the unique games conjecture, it is known that the approximation ratio and inapproximability ratio for constraint satisfaction problems is equal to the integrality gap of a simple SDP relaxation (see Optimal Algorithms and Inapproximability Results for Every CSP? by Prasad Raghavendra)

Finally, integrality gaps represent unconditional lower bounds. Usually, we need to rely on unproven assumptions (e.g. $P \neq NP$) if we want to make any progress in lower bounds, but for restricted models of computation, we can sometimes get away without it (see lecture notes by Luca Trevisan). Integrality gaps, being purely geometric rather than computational, are one way of getting fairly powerful lower bounds without the baggage of extra assumptions.

Answer 2

Suppose that your problem of interest is a minimization problem and that you have developed an $a$-approximate algorithm. If, on a given input, your algorithm outputs a solution of cost $c$, then the computation of the algorithm plus its analysis give a certificate that, on that input, the optimum is at least $a/c$. Clearly, $a$ is at least the optimum, so for every input we are able to certify a lower bound to the optimum which is at least a $1/c$ fraction of the optimum itself.

In all the algorithms based on convex (LP and SDP) relaxations that I am aware of, the certified lower bound to the optimum is given by the optimum of the relaxation. If the relaxation has integrality gap $I$, then it is not going to be possible to achieve an approximation ratio better than $I$, unless in the analysis one introduces a lower bound technique for the optimum that is stronger than the lower bound provided by the relaxation.

Answer 3

The integrality gap is a useful indicator of how well an IP can be approximated. It might be better to think of it in an informal, intuitive way. A high integrality gap implies that certain methods won't work. Certain primal/dual methods, for example, depend on a small integrality gap. For the standard primal Vertex Cover LP, the dual LP asks for a maximum matching. In this case, we can do the following:

• find an optimum fractional solution $\boldsymbol{y}$ to the dual LP (a maximum fractional matching)
• multiply the solution $\boldsymbol{y}$ by a factor of 2 (double all edge weights)
• convert this to a feasible integral $\boldsymbol{x}$ for the primal LP (each edge gives half of its weight from the $2\boldsymbol{y}$ vector to each of its endpoints in the $\boldsymbol{x}$ vector, then each $x_i$ is replaced with $\min(\lfloor x_i\rfloor, 1)$).

In this case this simple strategy works and we end up with a feasible integral solution to the primal LP whose weight is no more than twice the weight of a feasible solution for the dual LP. Since the weight of a feasible solution for the dual LP is a lower bound for OPT, this is a 2-approximation algorithm.

Now, where does the integrality gap come in? The IG is 2 in this case, but that alone doesn't imply that the algorithm will work. Rather, it suggests that it might work. And if the IG was more than 2, it would guarantee that the simple strategy would not always work. At the very least we would have to multiply the dual solution by the IG. So the integrality gap sometimes tells us what won't work. The integrality gap can also indicate what kind of approximation factor we can hope for. A small integrality gap suggests that investigating rounding strategies, etc., might be a worthwhile approach.

For a more interesting example, consider the Hitting Set problem and the powerful technique of approximating the problem using $\varepsilon$-nets (Brönnimann & Goodrich, 1995). Many problems can be formulated as instances of Hitting Set, and a strategy that has been successful for many problems is to do this, then just find a good net finder, i.e., an algorithm to construct small $\varepsilon$-nets, and crank everything through the B&G meta-algorithm. So people (myself included) try to find net finders for restricted instances of Hitting Set that, for any $\varepsilon$, can build an $\varepsilon$-net of size $f(1/\varepsilon)$, where the function $f$ should be as small as possible. Having $f(1/\varepsilon) = \mathcal{O}(1/\varepsilon)$ is a typical goal; this would give a $\mathcal{O}(1)$-approximation.

As it turns out, the best possible function $f$ is bounded by the integrality gap of a certain LP for Hitting Set (Even, Rawitz, Shahar, 2005). Specifically, the optimum integral and fractional solutions satisfy $\mathrm{OPT}_I \leq f(\mathrm{OPT}_f)$. For unrestricted instances of Hitting Set the integrality gap is $\Theta(\log(m))$, but when formulating another problem as Hitting Set, the IG can be lower. In this example the authors show how to find $\varepsilon$-nets of size $\mathcal{O}((1/\varepsilon) \log \log (1/\varepsilon))$ for the restricted instances of Hitting Set that correspond to the problem of hitting axis-parallel boxes. In this way they improve upon the best known approximation factor for that problem. It's an open problem whether or not this can be improved. If, for these restricted Hitting Set instances, the IG for the Hitting Set LP is $\Theta(\log \log m)$, it would be impossible to design net finder guaranteeing $\varepsilon$-nets of size $o((1/\varepsilon) \log \log (1/\varepsilon))$, since doing so would imply the existence of an algorithm that guarantees integral hitting sets of size $o(\mathrm{OPT}_f \log\log \mathrm{OPT}_f)$, but since $\mathrm{OPT}_f\leq m$ this would imply a smaller integrality gap. So if the integrality gap is large, proving it could prevent people from wasting their time looking for good net finders.

Answer 4

When you are coming up with an approximation algorithm for some NP-hard maximization problem, there are several values that you might care about: There is OPT, the optimal value of your problem, which is the same as OPT(IP), the optimal value of any correct IP formulation of your problem. There is also OPT(LP), the optimal value of the linear relaxation of your IP.

$OPT(LP) \geq OPT(IP)$

Finally, there is V, the value of the solution you end up getting by rounding the LP solution. You would like to be able to prove that $V > \frac{OPT(IP)}{c}$ to show that your algorithm is a $c$ approximation, but it is often not possible to do this directly, since you don't have a hold on the solution space. Instead, what is almost always proven is that $V \geq \frac{OPT(LP)}{c}$. This of course implies $V > \frac{OPT(IP)}{c}$, but is stronger. In particular, if the integrality gap of your IP formulation is larger than $c$, the above statement will be false in general, since your rounding procedure ends up with an integral solution.

So the crux is this: The LP gives you a solution which you know is "good", and you want to round it to something that is "almost as good". If the integrality gap is large, this is impossible in general, since there will never be a procedure which is guaranteed to get an integral solution that is "amost as good" as an LP solution -- because sometimes, these don't exist!

Answer 5

You are right in that the integrality gap of a relaxation has as such nothing to do with any rounding algorithm. These are two different notions. An integrality gap is a property of a particular relaxation. That is, how much larger is the value of that relaxation compared to the optimal integral value?

Why do we care about linear/convex relaxations? To efficiently approximate an integral value. Hence, we typicaly talk about relaxations only in cases where the optimal value is hard to compute and we're interested in efficient approximations. Integrality gaps show us the inherent limitations of what can be achieved by such techniques.

So, why do we care about rounding algorithms on top of the relaxation? We use rounding algorithms to solve the algorithmic problem of finding a near optimal solution as opposed to just approximating the value of an optimal solution. Moreover, often rounding algorithms are used to bound the integrality gap of a relaxation in the first place.

Answer 6

Technically, the integrality gap is for a specific IP formulation, not (as you formulated it) the ration between the best linear relaxation and the optimal solution (which appears to quantify over ALL IP formulations).

An integrality gap is important because it shows the limits of the particular LP formulation being used. If I know that that a particular relaxation has an integrality gap of $c$, then I also know that if I ever hope to prove a bound of better than $c$, I'll need to use a different formulation.

Answer 7

There was a very interesting paper "On the advantage of network coding for improving network throughput" which showed that the integrality gap of the "bidirected cut relaxation" for the Steiner tree problem exactly equals a type of "coding advantage" in network communication. I don't know of a lot of other similar papers. However, one should also note that seemingly better LP relaxations for the Steiner tree problem are known (e.g. see the new hypergraphic LP-based approximation algorithm of Byrka et al in STOC 2010, I also shamelessly volunteer that I coauthored some recent papers studying the hypergraphic LP).

Answer 8

Most answers have already addressed the main reason to care about the integrality gap, namely, that an approximation algorithm based solely on using the bound provided by the relaxation cannot hope to prove a ratio better than the integrality gap. Let me give two other meta reasons why the integrality gap is a useful guide. For a large class of combinatorial optimization problems the equivalence of separation and optimization shows that exact algorithms are intimately related to the convex hull of the feasible solutions for the problem. Thus the geometric and algorithmic perspective are very closely tied together. A similar formal equivalence is not known for approximation algorithms but it is a useful guide - algorithms go hand in hand with geometric relaxations. Algorithmic innovation happens when people have a concrete target to improve. Integrality gap is one such target and attempts to find better gaps has resulted in improved relaxations for various problems which in turn led to improved approximation algorithms for those problems.