Approximation algorithms for buy-at-bulk geometric network design
(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:
https://lup.lub.lu.se/record/1670324
- author
- Czumaj, Artur ; Czyzowicz, Jurek ; Gasieniec, Leszek ; Jansson, Jesper LU ; Lingas, Andrzej LU and Zylinski, Pawel
- organization
- publishing date
- 2011
- 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
- 0302-9743
- 1611-3349
- 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 = {{0302-9743}}, 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}}, }