Proving integral gap of linear programs are generally hard. It would be great if one can classify LPs with a constant gap. It is known that deciding whether a polyhedron is integral is co-NP-complete [1]. I am interested in techniques for proving constant upperbound for integral gaps of linear programs.

Here are some methods with examples that I read in books and papers.

1 Counting

Just do the counting.

An example would be the celebrated tree packing theorem.

Note that the optimum solution to $\lambda$ is the minimum cut in $G$. It is known that $\tau$ is the maximum tree packing in $G$ and $\tau =\underset{F\subset E}{\min }\frac{|E-F|}{r(E)-r(F)}$, where $r$ is the rank of the graphic matroid on $G$ [2]. Then the proof is a simple counting argument.

A stronger example is the $k$-cut LP.

The proof is in section 5 of [3]. Here is a sketch.

For $k$-cut we cannot use the simple counting argument since the dual LP is not a tree packing. (the LP dual needs extra variables $z_e$ for constraints $x_e\le 1$.) However, it is still easy to find an upperbound for the integral optimum. If we sort vertices in increasing order of their degree, that is, $\mathrm{deg}(v_1)\le \cdots \le \mathrm{deg}(v_n)$, then ${\sum }_{i=1}^{k-1}\mathrm{deg}(v_i)$ is an upperbound for integral $k$-cut. Then it is easy to prove that if the optimal solution $x^{\ast }$ to ${\lambda }_k$ is fully fractional ($x_e^{\ast }\in (0,1)$ for all $e\in E$), then the gap is $2(1-1/n)$. The proof is to use complemantary slackness conditions, i.e., $z_e=0,{\sum }_{e\in T}{y}_T=c(e)\forall e\in E$. The following observations reduce general $x^{\ast }$ to fully fractional case:

1. Given an optimal solution $x^{\ast }$, let $X$ be the set of edges $e$ such that $x_e^{\ast }=0$. The optimum to ${\lambda }_k$ on $G/X$ is the same as on $G$.
2. For an optimal solution $x^{\ast }$, let $F$ be the set of edges $e$ such that $x_e^{\ast }=1$. Let $x^{\ast }{|}_{E-F}$ be the restriction of $x^{\ast }$ to $E-F$. $x^{\ast }{|}_{E-F}$ is a fully fractional optimum solution to ${\lambda }_k$. (Some discussions are needed for the number of components in $G\setminus F$. The reduction can be done using the fact that if $1\le \frac{\lambda }{\sigma }\le c$ then $1\le \frac{\lambda +k}{\sigma +k}\le c$.)

2 Approximation algorithm

A constant factor approximation algorithm based on LP may imply a constant upperbound of the corresponding LP.

Examples:

1. vertex cover and set cover: https://courses.grainger.illinois.edu/cs598csc/sp2011/Lectures/lecture_4.pdf
2. facility location: https://www.cs.dartmouth.edu/~deepc/LecNotes/Appx/5.%20Deterministic%20Rounding%20for%20Facility%20Location.pdf

3 Intermediate problem

I read this in [4]. Suppose that we want to prove constant gap for $LP1$. The idea is to find another LP (say $LP2$) which is integral or has constant gap and to prove that $\frac{\mathrm{OPT}(IP1)}{\mathrm{OPT}(IP2)}\le c_1$ and $\frac{\mathrm{OPT}(LP2)}{\mathrm{OPT}(LP1)}\le c_2$. Finally we will have something like this,

$$\begin{array}{c}\mathrm{OPT}(IP1)\le c_1\mathrm{OPT}(IP2)=c_1\mathrm{OPT}(LP2)\le c_1{c}_2\mathrm{OPT}(LP1)\end{array}$$

The example in [4] is finding the minimum $k$-edge-connected spanning subgraph.

We want to prove that the integral gap for the following LP is 2.

$$\begin{array}{rlrlrl}LP1=\min & & \sum _{e\in E}w(e& )x_e& & \\ s.t.& & \sum _{e\in C}{x}_e& \ge k& & \forall \text{cut C}\\ & & 0\le x_e& \le 1& & \forall e\in E\end{array}$$

(Finding the minimum $k$-edge-connected spanning subgraph of $G=(V,E)$)

Now we construct LP2. Consider the bidirection version of $G$, denoted by $D=(V,A)$ where $A=\{(u,v),(v,u)\forall (u,v)\in E\}$. Pick a special vertex $r$.

$$\begin{array}{rlrlrl}LP2=\min & & \sum _{e\in A}w(e)& y_e& & \\ s.t.& & \sum _{e\in {\delta }^{+}(S)}{y}_e& \ge k& & \forall S\subset V\wedge r\in S\\ & & 0\le y_e& \le 1& & \forall e\in E\end{array}$$

(Finding min k-arborescence)

It is known that the polytope in LP2 is integral [2]. Given any feasible solution of LP, for any edge $e=(u,v)\in E$ we set $y_{(u,v)}=y_{(v,u)}=x_e$. Thus the optimum of LP2 is no larger than $2\mathrm{OPT}(LP)$ since $y$ is always feasible.

On the other hand, given a feasible integral solution $y$ of LP2, we set $x_e=1$ if any orientation of $e$ is in $y$. It is clear from the definition of LP2 that $x_e$ is a feasible integral solution of LP. Hence, applying eq(1) proves that the integral gap of LP is 2. (Note that in this example $c_1=1$ and $c_2=2$.)

Notes

There are many discussions about the integrality gap on cstheory.

1. https://cstheory.stackexchange.com/questions/30984/exactly-solvable-but-non-trivial-integrality-gap
2. https://cstheory.stackexchange.com/questions/4915/integrality-gap-and-approximation-ratio
3. https://cstheory.stackexchange.com/questions/392/the-importance-of-integrality-gap
4. https://cstheory.stackexchange.com/questions/55188/randomized-rounding-schemes-that-depend-on-the-weights-in-the-lp-objective
5. https://cstheory.stackexchange.com/questions/21060/optimization-problems-with-minimax-characterization-but-no-polynomial-time-algo
6. https://cstheory.stackexchange.com/questions/3871/minimum-maximal-solutions-of-lps

It seems that the integrality gap has a deep connection with hardness of approximation. I believe this kind of connections is more than empirical observations.

References