The Library
Approximation algorithms for buy-at-bulk geometric network design
Tools
Tools
Tools
Czumaj, Artur, Czyzowicz, Jurek, Gasieniec, Leszek, Jansson, Jesper, Lingas, Andrzej and Zylinski, Pawel (2009) Approximation algorithms for buy-at-bulk geometric network design. In: 11th International Workshop on Algorithms and Data Structures (WADS 2009), Banff, Canada, August 21-23, 2009. Published in: Lecture Notes in Computer Science, Vol.5664 pp. 168-180.
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-642-03367-4
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.
| Item Type: | Conference Item (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Computer Science |
| Series Name: | Lecture Notes in Computer Science |
| Journal or Publication Title: | Lecture Notes in Computer Science |
| Publisher: | Springer |
| ISBN: | 978-3-642-03366-7 |
| ISSN: | 0302-9743 |
| Editor: | Dehne, F and Gavrilova, M and Sack, JR and Toth, CD |
| Date: | 2009 |
| Volume: | Vol.5664 |
| Number of Pages: | 13 |
| Page Range: | pp. 168-180 |
| Identification Number: | 10.1007/978-3-642-03367-4 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Conference Paper Type: | Paper |
| Title of Event: | 11th International Workshop on Algorithms and Data Structures (WADS 2009) |
| Type of Event: | Conference |
| Location of Event: | Banff, Canada |
| Date(s) of Event: | August 21-23, 2009 |
| URI: | http://wrap.warwick.ac.uk/id/eprint/17276 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
