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?
The importance of Integrality Gap
cc.complexity theory;ds.algorithms;approximation algorithms;linear programming;integrality gap