Tags: optimization, LP

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.

1.1 tree packing theorem

Example1

Consider the following integer program on graph $G=(V,E)$, \[\begin{align*} \lambda=\min& & \sum_{e\in E} x_e& & & \\ s.t.& & \sum_{e\in T} x_e&\ge 1 & &\forall T\in \mathcal T \\ & & x_e&\in\Z_{\ge 0} & &\forall e\in E \end{align*}\]

where $\mathcal T$ is the set of spanning tree in $G$. Let $\tau$ be the optimum of the linear relaxation.

Theorem2

$\lambda \le 2 \tau$.

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=\min\limits_{F\subset E}\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.

Proof

If $G$ is not connected, Let $G_1,...,G_k$ be the set of components in $G$. One can easily see that the gap of $G$ is at most the largest gap of the components. Thus considering connected graphs is sufficient.

We fix $F^*\in \arg\min \frac{|E-F^*|}{r(E)-r(F^*)}$. $r(E)-r(F^*)$ must be positive and $E-F^*$ is a cut in $G$. Suppose $E-F^*$ is any cut in $G$. Let $S_1,...,S_h$ be components in $G\setminus (E\setminus F^*)$. For any $S_i$, the set of edges with exactly one endpoint in $S_i$ (denoted by $e[S_i]$) must contain a cut of $G$ since the $G$ is connected. One can see that $2|E-F^*|=\sum_i |e[S_i]|\ge \lambda (r(E)-r(F))$ since the number of component is $r(E)-r(F^*)$.

1.2 $k$-cut

Example3

\[\begin{align*} \lambda_k=\min& & \sum_{e\in E} c(&e)x_e & & \\ s.t.& & \sum_{e\in T} x_e&\ge k & &\forall T\in \mathcal T \\ & & 0\le x_e&\le 1 & &\forall e\in E \end{align*}\]

Theorem4

The integral gap of $\lambda_k$ is at most $2(1-1/n)$.

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, $\mathop{\mathrm{deg}}(v_1)\le \dots \le \mathop{\mathrm{deg}}(v_n)$, then $\sum_{i=1}^{k-1} \mathop{\mathrm{deg}}(v_i)$ is an upperbound for integral $k$-cut. Then it is easy to prove that if the optimal solution $x^*$ to $\lambda_k$ is fully fractional ($x_e^*\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^*$ to fully fractional case:

Given an optimal solution $x^*$, let $X$ be the set of edges $e$ such that $x_e^*=0$. The optimum to $\lambda_k$ on $G/X$ is the same as on $G$.
For an optimal solution $x^*$, let $F$ be the set of edges $e$ such that $x_e^*=1$. Let $x^*|_{E-F}$ be the restriction of $x^*$ to $E-F$. $x^*|_{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\leq \frac{\lambda}{\sigma}\le c$ then $1\le \frac{\lambda+k}{\sigma+k}\le c$.)

2 Rounding

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

Examples:

vertex cover. simple threshold rounding or the LP structure (there is a half integral optimal solution)
facility location. Dartmouth
CKR relaxation of multiway cut uiuc cs583 sp18
uniform labeling (multiway cut with assignment cost) FOCS’99
generalized steiner network problem with skew-supermodular requirements. iterative rounding. uiuc cs598 sp09

3 Intermediate problem

I read about 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{\mathop{\mathrm{OPT}}(IP1)}{\mathop{\mathrm{OPT}}(IP2)}\le c_1$ and $\frac{\mathop{\mathrm{OPT}}(LP2)}{\mathop{\mathrm{OPT}}(LP1)}\le c_2$. Finally we will have something like this,

\[\begin{equation} \mathop{\mathrm{OPT}}(IP1)\le c_1\mathop{\mathrm{OPT}}(IP2)\le c_1 \mathop{\mathrm{OPT}}(LP2)\le c_1 c_2 \mathop{\mathrm{OPT}}(LP1) \end{equation}\]

3.1 minimum $k$-edge-connected spanning subgraph

This problem is a special case of 5 in the rounding part.

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

\[\begin{align*} 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{align*}\]

(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) \quad \forall (u,v)\in E\}$. Pick a special vertex $r$.

\[\begin{align*} 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 \land r\in S\\ & & 0\le y_e &\le 1 & &\forall e\in E \end{align*}\]

(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\mathop{\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$.)

4 Notes

There are many discussions about the integrality gap on cstheory.

It seems that the integrality gap has a deep connection with hardness of approximation. There are two kinds of problems that i find particularly interesting.

The LP has a relatively large gap, but some algorithm based on that LP achieves a better approximation than the gap.(see this FOCS’09 paper)
The integrality gap is small (a constant), but approximation algs based on the LP cannot do that good. (Zhiyi Huang gave a talk at UESTC recently. https://arxiv.org/abs/2509.17029 The correlated Pandora’s problem has a natural LP formulation with gap $<4$, while it is NP-hard to aproximate it within a ratio of $4-\epsilon$.)

References

[1]

G. Ding, L. Feng, W. Zang, The complexity of recognizing linear systems with certain integrality properties, Mathematical Programming. 114 (2008) 321–334 10.1007/s10107-007-0103-y.

[2]

A. Schrijver, Combinatorial optimization Polyhedra and Efficiency, Springer, 2004.

[3]

C. Chekuri, K. Quanrud, C. Xu, LP Relaxation and Tree Packing for Minimum $k$-Cut, SIAM Journal on Discrete Mathematics. 34 (2020) 1334–1353 10.1137/19M1299359.

[4]

P. Chalermsook, C.-C. Huang, D. Nanongkai, T. Saranurak, P. Sukprasert, S. Yingchareonthawornchai, Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver, in: 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022: pp. 37:1–37:20 10.4230/LIPIcs.ICALP.2022.37.

Proving integrality gap for LPs