Approximation algorithms for network design: A survey

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.