New class of 0–1 integer programs with tight approximation via linear relaxations

We consider the problem of estimating optima of integer programs {max cx | Ax ≤ b, 0 ≤ x ≤ 1, x integral} where b > 0, c ≥ 0 are rational vectors and A is an arbitrary rational m × n matrix. Using randomized rounding we find an efficiently verifiable sufficient condition for optima of such integer programs to be close to the optima q of their linear relaxations. We show that our condition guarantees that for any constant ϵ > 0 and sufficiently large n there exists a feasible integral solution z such that q ≥ cz ≥ (1 − ϵ)q.