Publications Details
Strengthening integrality gaps for capacitated network design and covering problems
A capacitated covering integer programs (IP) is an integer program of the form min{cx|Ux≥d, 0≤x≤b, x∈Z+}, where all entries of c, U and d are nonnegative. Given such a formulation, the ratio between the optimal integer solution and the optimal solution to the linear program relaxation can be as bad as ∥d∥, even when U consists of a single row. It is shown that by adding additional inequalities, this ratio can be improved significantly. In the general case, the improved ratio is shown to be bounded by the maximum number of non-zero coefficients in a row of U, and a polynomial-time approximation is proved to achieve this bound.