Simpler and better approximation algorithms for network design

Anupam Gupta, Amit Kumar, Tim Roughgarden

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)365-372
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2003
Event35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States
Duration: Jun 9 2003Jun 11 2003


  • Approximation algorithms
  • Network design
  • Randomized algorithms

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Simpler and better approximation algorithms for network design'. Together they form a unique fingerprint.

Cite this