Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Approximation algorithms for buy-at-bulk geometric network design

Czumaj, Artur ; Czyzowicz, Jurek ; Gasieniec, Leszek ; Jansson, Jesper LU ; Lingas, Andrzej LU and Zylinski, Pawel (2011) 11th International Symposium, WADS 2009 5664. p.1949-1969
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.
Please use this url to cite or link to this publication:
author
; ; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Algorithms and data structures / Lecture notes in computer science
volume
5664
pages
1949 - 1969
publisher
Springer
conference name
11th International Symposium, WADS 2009
conference location
Banff, Canada
conference dates
2009-08-21 - 2009-08-23
external identifiers
  • wos:000299094200014
  • scopus:69949182886
ISSN
1611-3349
0302-9743
ISBN
3-642-03366-0
DOI
10.1007/978-3-642-03367-4_15
project
VR 2008-4649
language
English
LU publication?
yes
id
50df1ab8-4319-49ad-a687-80ce4fad4fd7 (old id 1670324)
date added to LUP
2016-04-01 11:06:34
date last changed
2024-03-10 15:24:37
@inproceedings{50df1ab8-4319-49ad-a687-80ce4fad4fd7,
  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.}},
  author       = {{Czumaj, Artur and Czyzowicz, Jurek and Gasieniec, Leszek and Jansson, Jesper and Lingas, Andrzej and Zylinski, Pawel}},
  booktitle    = {{Algorithms and data structures / Lecture notes in computer science}},
  isbn         = {{3-642-03366-0}},
  issn         = {{1611-3349}},
  language     = {{eng}},
  pages        = {{1949--1969}},
  publisher    = {{Springer}},
  title        = {{Approximation algorithms for buy-at-bulk geometric network design}},
  url          = {{http://dx.doi.org/10.1007/978-3-642-03367-4_15}},
  doi          = {{10.1007/978-3-642-03367-4_15}},
  volume       = {{5664}},
  year         = {{2011}},
}