Approximation algorithms for network design: A survey

Anupam Gupta; Jochen Könemann

doi:10.1016/j.sorms.2010.06.001

Approximation algorithms for network design: A survey

Anupam Gupta, Jochen Könemann

Computer Science

Research output: Contribution to journal › Review article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	3-20
Number of pages	18
Journal	Surveys in Operations Research and Management Science
Volume	16
Issue number	1
DOIs	https://doi.org/10.1016/j.sorms.2010.06.001
State	Published - Jan 2011

ASJC Scopus subject areas

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

Access to Document

10.1016/j.sorms.2010.06.001

Cite this

@article{4bf3cf7b779d4e6c8a9241fbdda78b38,

title = "Approximation algorithms for network design: A survey",

abstract = "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.",

author = "Anupam Gupta and Jochen K{\"o}nemann",

year = "2011",

month = jan,

doi = "10.1016/j.sorms.2010.06.001",

language = "English (US)",

volume = "16",

pages = "3--20",

journal = "Surveys in Operations Research and Management Science",

issn = "1876-7354",

publisher = "Elsevier Limited",

number = "1",

}

TY - JOUR

T1 - Approximation algorithms for network design

T2 - A survey

AU - Gupta, Anupam

AU - Könemann, Jochen

PY - 2011/1

Y1 - 2011/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77957236913&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957236913&partnerID=8YFLogxK

U2 - 10.1016/j.sorms.2010.06.001

DO - 10.1016/j.sorms.2010.06.001

M3 - Review article

AN - SCOPUS:77957236913

SN - 1876-7354

VL - 16

SP - 3

EP - 20

JO - Surveys in Operations Research and Management Science

JF - Surveys in Operations Research and Management Science

IS - 1

ER -

Approximation algorithms for network design: A survey

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this