Approximation algorithms for buy-at-bulk geometric network design

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

doi:10.1007/978-3-642-03367-4_15

Approximation algorithms for buy-at-bulk geometric network design

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

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 language	English (US)
Title of host publication	Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
Pages	168-180
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-03367-4_15
State	Published - 2009
Externally published	Yes
Event	11th International Symposium on Algorithms and Data Structures, WADS 2009 - Banff, AB, Canada Duration: Aug 21 2009 → Aug 23 2009

Publication series

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

Conference

Conference	11th International Symposium on Algorithms and Data Structures, WADS 2009
Country/Territory	Canada
City	Banff, AB
Period	8/21/09 → 8/23/09

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-03367-4_15

Cite this

Czumaj, A., Czyzowicz, J., Ga̧sieniec, L., Jansson, J., Lingas, A., & Zylinski, P. (2009). Approximation algorithms for buy-at-bulk geometric network design. In Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings (pp. 168-180). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5664 LNCS). https://doi.org/10.1007/978-3-642-03367-4_15

Approximation algorithms for buy-at-bulk geometric network design. / Czumaj, Artur; Czyzowicz, Jurek; Ga̧sieniec, Leszek et al.
Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. 2009. p. 168-180 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5664 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Czumaj, A, Czyzowicz, J, Ga̧sieniec, L, Jansson, J, Lingas, A & Zylinski, P 2009, Approximation algorithms for buy-at-bulk geometric network design. in Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5664 LNCS, pp. 168-180, 11th International Symposium on Algorithms and Data Structures, WADS 2009, Banff, AB, Canada, 8/21/09. https://doi.org/10.1007/978-3-642-03367-4_15

Czumaj A, Czyzowicz J, Ga̧sieniec L, Jansson J, Lingas A, Zylinski P. Approximation algorithms for buy-at-bulk geometric network design. In Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. 2009. p. 168-180. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03367-4_15

Czumaj, Artur ; Czyzowicz, Jurek ; Ga̧sieniec, Leszek et al. / Approximation algorithms for buy-at-bulk geometric network design. Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. 2009. pp. 168-180 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9799163366b24a07afde39106529f3a6,

title = "Approximation algorithms for buy-at-bulk geometric network design",

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 = "Artur Czumaj and Jurek Czyzowicz and Leszek G{\c a}sieniec and Jesper Jansson and Andrzej Lingas and Pawel Zylinski",

year = "2009",

doi = "10.1007/978-3-642-03367-4_15",

language = "English (US)",

isbn = "3642033660",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "168--180",

booktitle = "Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings",

}

TY - GEN

T1 - Approximation algorithms for buy-at-bulk geometric network design

AU - Czumaj, Artur

AU - Czyzowicz, Jurek

AU - Ga̧sieniec, Leszek

AU - Jansson, Jesper

AU - Lingas, Andrzej

AU - Zylinski, Pawel

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=69949182886&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=69949182886&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03367-4_15

DO - 10.1007/978-3-642-03367-4_15

M3 - Conference contribution

AN - SCOPUS:69949182886

SN - 3642033660

SN - 9783642033667

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 168

EP - 180

BT - Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings

T2 - 11th International Symposium on Algorithms and Data Structures, WADS 2009

Y2 - 21 August 2009 through 23 August 2009

ER -

Approximation algorithms for buy-at-bulk geometric network design

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this