Simpler and Better Approximation Algorithms for Network Design

Gupta, Kumar, Roughgarden, STOC (2003), http://www.cs.cornell.edu/timr/papers/simple.ps

Abstract (of the paper): We give simple and easy­to­analyze randomized approximation algorithms for several well­studied NP­hard network design problems. Our algorithms improve over the previously best known approximation ratios. Our main results are the following. We give a randomized 3.55­approximation algorithm for the connected facility location problem. The algorithm requires three lines to state, one page to analyze, and improves the best­known performance guarantee for the problem. We give a 5.55­approximation algorithm for virtual private network design. Previously, constant­factor approximation algorithms were known only for special cases of this problem. We give a simple constant­factor approximation algorithm for the single­sink buy­at­bulk network design problem. Our performance guarantee improves over what was previously known, and is an order of magnitude improvement over previous combinatorial approximation algorithms for the problem.