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: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic 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 the geometric version of the problem, where all points in a Euclidean space are candidates for network nodes. We present the first general approach for geometric versions of basic variants of the buy-at-bulk network design problem. 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 few sinks and low capacity links, we design very fast polynomial-time low-constant approximations algorithms.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
Pages168-180
Number of pages13
DOIs
Publication statusPublished - 14 Sep 2009
Externally publishedYes
Event11th International Symposium on Algorithms and Data Structures, WADS 2009 - Banff, AB, Canada
Duration: 21 Aug 200923 Aug 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5664 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Symposium on Algorithms and Data Structures, WADS 2009
Country/TerritoryCanada
CityBanff, AB
Period21/08/0923/08/09

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this