Basic requirements for Integrality gap examples

Question

I have the following question about giving a series of examples of range spaces for my Hitting Set problem that establish a lower bound for the integrality gap (IG).

IG is the supremum of ratio of the optimum for natural integer linear programming (ILP) formulation of Hitting Set to the optimum for its (mean ILP) LP-relaxation taken over all range spaces corresponding to my problem.

There are lots of algorithms where solution for LP-relaxation is rounded to some feasible solution of ILP which is not far from optimum. IG gives the lower bound of multiplicative factor to which rounding procedure could worsen the optimum for LP with respect to the goal function.

Specifically, do I need to provide any polynomial algorithm for generating those series of example range spaces (giving the gap lower bound) ? if yes, then what are the parameters with respect to which my algorithm should be polynomial in ? I'm interested in this because by claiming some gap lower bound I provide educated lower bound for approximation algorithm performances which are based on aforementioned LP-relaxation.

Answer 1

No, there is absolutely no need for the gap instances to be efficiently constructible. It is perfectly fine even to give some pure existence proof, say using diagonalization or probabilistic techniques.

The reason is that the integrality gap examples rule out certain kinds of algorithms. Specifically, suppose that an algorithm solves the LP and then rounds it, and suppose that the way you prove the approximation guarantee is by showing (for a minimization problem) that rounding increases the value of the solution by at most a factor $C$. If there is an integrality gap of $\alpha$ then you know that $C \geq \alpha$. So no algorithm with this kind of analysis can result in an approximation ratio better than $\alpha$.

If I remember correctly there are some rare cases in which the way you analyze your algorithm is a bit different, and then you can go beyond the integrality gap, but unfortunately I can't think of any; if you're interested ask a separate question.

It is meaningful to consider an integrality gap even for different relaxations, for example for the semidefinite relaxation or for some LP or SDP hierarchy. The requirements are the same only you're comparing the integral optimum to the value of some more complicated program. The consequence is that an algorithm which proceeds by solving that program and then rounding can't given an approximation ratio better than the integrality gap (unless it does some rare hocus pocus as mentioned above).

Chlamtac and Tulsiani have written a nice survey on integrality gaps, which you might want to browse. It describes many complicated methods for constructing integrality gaps.