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\mathbb{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

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^*

\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