One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my LP relaxation.

As far as my knowledge goes, integrality gap for maximization problem is the the maximum ratio cost(LP)/cost(ILP) over all instances of a problem. But I've been googling for a little bit, and most examples only showed how to get a lower bound of integrality gap by taking some arbitrary instance. Is it possible to get an exact ratio?


Suppose you prove that an upper bound on the integrality gap is $\alpha$. The goal is to “create” an instance (weighted graph, or better yet, a family of weighted graphs) where the value of the optimal LP solution is $\alpha$ times the value of the ILP solution.

Independent set ILP $$O_{ILP}=\max\sum_{v\in V}x_{v}\cdot w(v) $$
such that
$$x_{v}+x_{u} \leq 1\ \ \ \forall u,v\in V$$ $$x_{v}\in\{0,1\} \ \ \forall v\in V$$

The relaxation is straight forward. say the value of the optimal solution to the LP is $O_{LP}.$ Now, you want to upper bound $ O_{LP}/O_{ILP}.$ To do this, try to consider a rounding scheme that converts a solution for the LP into a feasible solution for the corresponding ILP. One such scheme involves reasoning about the constraints, that is $x_{v}+x_{u}\leq1$ for every edge in G. This implies that at least one of $x_{u}$ or $x_{v}$ is atleast $1/2$, and therefore all vertices in $v\in V$ such that $x_{v}>\frac{1}{2}$ is an independent set in $G$. I'll leave it to you to reason about how to compare $O_{LP}$ and $O_{ILP}$, (i.e. determine the maximum of the ratio $\alpha=\max O_{LP}/O_{ILP}$), and to find an instance where $O_{LP}$ is atleast $\alpha.$

  • $\begingroup$ What you left me as an exercise was my whole point of the question, but thanks. I'll try it. $\endgroup$ – Ted Nov 25 '17 at 22:04
  • $\begingroup$ I guess if you have all vertices in a graph assigned weight exactly 1/2 by the LP, then you will have issues since no edge constraint would be violated. So consider the complete graph and assign whatever values you want to the vertices (say each has weight $M$ in the graph) then $O_{LP}$ is $(n \cdot M)/2$ but $OPT_{ILP}=M$ so the integrality gap is actually $n/2$. $\endgroup$ – mm8511 Nov 25 '17 at 22:41
  • $\begingroup$ @Ted No problem. Sorry I missed the point of your question initially. I originally thought you were confused about the rounding part. $\endgroup$ – mm8511 Nov 26 '17 at 16:34

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.