Strengthening the Integrality Gaps for Capacitated Network Design and Covering Problems

costs and capacities, the capacitated network design problem is
to select the minimum cost set of edges so that the minimum
capacity cut in the resulting network that separates any vertex
pair is at least the demand of the vertex pair.

This problem is NP-hard. Minimum cost steiner tree is a very special
case. In this setting, it is desirable to have a fast algorithm
that provides a solution that is guaranteed to come close to the optimal
solution. The best previous known approximation algorithm
for this problem is an m-approximation, where m is the size of the
initial edge set.

We give improved approximation algorithms that are based on a tightened
LP-relaxation and reduced gap between the optimal solutions to the
IP and the LP. Our proof technique extends
to some more general covering problems.

This is joint work with Bob Carr, Cindy Phillips, and Vitus Leung,
all of Sandia National Laboratories, Albuquerque, USA.