The Library
Approximation algorithms for soft-capacitated facility location in capacitated network design
Tools
Tools
Tools
Chen, Xujin and Chen, Bo, Dr.. (2009) Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica, Vol.53 (No.3). pp. 263-297. ISSN 0178-4617
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-007-9032-7
Abstract
Answering an open question published in Operations Research (54, 73-91, 2006) in the area of network design and logistic optimization, we present the first constant-factor approximation algorithms for the problem combining facility location and cable installation in which capacity constraints are imposed on both facilities and cables. We study the problem of designing a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment. Both facilities and cables have capacity constraints and incur buy-at-bulk costs. This Max SNP-hard problem arises in diverse applications and is shown in this paper to admit a combinatorial 19.84-approximation algorithm of cubic running time. This is achieved by an integration of primal-dual schema, Lagrangian relaxation, demand clustering and bi-factor approximation. Our techniques extend to several variants of this problem, which include those with unsplitable demands or requiring network connectivity, and provide constant-factor approximate algorithms in strongly polynomial time.
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Divisions: | Faculty of Social Sciences > Warwick Business School |
| Journal or Publication Title: | Algorithmica |
| Publisher: | Springer Verlag |
| ISSN: | 0178-4617 |
| Date: | March 2009 |
| Volume: | Vol.53 |
| Number: | No.3 |
| Number of Pages: | 35 |
| Page Range: | pp. 263-297 |
| Identification Number: | 10.1007/s00453-007-9032-7 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| URI: | http://wrap.warwick.ac.uk/id/eprint/28441 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
