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.