Approximation via cost sharing: Simpler and better approximation algorithms for network design

Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden

Research output: Contribution to journalArticlepeer-review

Abstract

We present constant-factor approximation algorithms for several widely-studied NP-hard optimization problems in network design, including the multicommodity rent-or-buy, virtual private network design, and single-sink buy-at-bulk problems. Our algorithms are simple and their approximation ratios improve over those previously known, in some cases by orders of magnitude. We develop a general analysis framework to bound the approximation ratios of our algorithms. This framework is based on a novel connection between random sampling and game-theoretic cost sharing.

Original languageEnglish (US)
Article number1236458
JournalJournal of the ACM
Volume54
Issue number3
DOIs
StatePublished - Jun 1 2007

Keywords

  • Approximation algorithms
  • Cost sharing
  • Network design
  • Random sampling

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint

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

Cite this