Approximation algorithms for network design: A survey

Anupam Gupta, Jochen Könemann

Research output: Contribution to journalReview articlepeer-review


Network Design is an active research area in the intersection of Combinatorial Optimization and Theoretical Computer Science that focuses on problems arising in the realm of modern communication networks. During the last 30 years of research in this field a number of major techniques have emerged; the aim of this article is to provide a survey of some of them. Each section concentrates on one technique; we first illustrate it using the well-known minimum spanning tree problem, and then present an advanced application.

Original languageEnglish (US)
Pages (from-to)3-20
Number of pages18
JournalSurveys in Operations Research and Management Science
Issue number1
StatePublished - Jan 2011

ASJC Scopus subject areas

  • Information Systems
  • Economics and Econometrics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Approximation algorithms for network design: A survey'. Together they form a unique fingerprint.

Cite this