The Library
Approximation algorithms for buy-at-bulk geometric network design
Tools
Tools
Tools
Czumaj, Artur, Czyzowicz, J., Gąsieniec, L., Jansson, J., Lingas, Andrzej and Zylinski, P. (2009) Approximation algorithms for buy-at-bulk geometric network design. In: Dehne, F. and Gavrilova, M. and Sack, J. R. and Toth, C. D., (eds.) Algorithms and data structures. Lecture Notes in Computer Science, Volume 5664 . Springer, pp. 168-180. ISBN 9783642033667
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
fulltext26.pdf - Published Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (269Kb) |
Official URL: http://dx.doi.org/10.1007/978-3-642-03367-4_15
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: | Book Item | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Journal or Publication Title: | Algorithms and Data Structures | ||||
| Publisher: | Springer | ||||
| ISBN: | 9783642033667 | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Algorithms and data structures | ||||
| Editor: | Dehne, F. and Gavrilova, M. and Sack, J. R. and Toth, C. D. | ||||
| Official Date: | 2009 | ||||
| Dates: |
|
||||
| Volume: | Volume 5664 | ||||
| Page Range: | pp. 168-180 | ||||
| DOI: | 10.1007/978-3-642-03367-4_15 | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Date of first compliant deposit: | 21 December 2015 | ||||
| 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
