Improved approximation algorithms for network design problems

Abstract

We consider a class of network design problems in which one needs to find a minimum-cost network satisfying certain connectivity requirements. For example, in the survivable network design problem, the requirements specify that there should be at least r(v; w) edge-disjoint paths between each pair of vertices v and w. We present an approximation algorithm with a performance guarantee of 2H(fmax ) = 2(1 + 2 + 3 + \\Delta \\Delta \\Delta + fmax ) where fmax is the maximum requirement. This improves upon the best previously known performance guarantee of 2fmax . We also show