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.