Approximation algorithms for buy-at-bulk geometric network design

Artur Czumaj, Jurek Czyzowicz, Leszek Ga̧sieniec, Jesper Andreas Jansson, Andrzej Lingas, Pawel Zylinski

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

The buy-at-bulk network design problem has been extensively studied in the general graph model. In this paper, we consider geometric versions of the problem, where all points in a Euclidean space are candidates for network nodes, and present the first general approach for solving them. It enables us to obtain quasi-polynomial-time approximation schemes for basic variants of the buy-at-bulk geometric network design problem with polynomial total demand. Then, for instances with a single sink and low capacity links, we design fast polynomial-time, low-constant approximation algorithms.
Original languageEnglish
Pages (from-to)1949-1969
Number of pages21
JournalInternational Journal of Foundations of Computer Science
Volume22
Issue number8
DOIs
Publication statusPublished - 1 Dec 2011
Externally publishedYes

Keywords

  • approximation algorithm
  • belt decomposition
  • buy-at-bulk
  • dynamic programming
  • Geometric networks
  • Hanan grid
  • quasi-polynomial- time approximation scheme (QPTAS)

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Cite this