# Basic requirements for Integrality gap examples

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.

• Wow. That first paragraph is ... hard to parse. I have no idea what this question is about. – Raphael Oct 29 '15 at 18:31

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$.