Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems

摘要

A capacitated covering IP is an integer program of the form min(l brace)ex(vert bar)Ux (ge) d, 0 (le) x (le) b, x (element of) Z(sup +)(r brace), 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 (parallel)d(parallel)(sub (proportional to)), even when U consists of a single row. They show that by adding additional inequalities, this ratio can be improved significantly. In the general case, they show that the improved ratio is bounded by the maximum number of non-zero coefficients in a row of U, and provide a polynomial-time approximation algorithm to achieve this bound. This improves upon the results of Bertsimas and Vohra, strengthening their extension of Hall and Hochbaum.