The Library
Approximation algorithms for soft-capacitated facility location in capacitated network design
Tools
Tools
Tools
Chen, Xujin and Chen, Bo (2009) Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica, Vol.53 (No.3). pp. 263-297. doi:10.1007/s00453-007-9032-7 ISSN 0178-4617.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 | ||||
| Official Date: | March 2009 | ||||
| Dates: |
|
||||
| Volume: | Vol.53 | ||||
| Number: | No.3 | ||||
| Number of Pages: | 35 | ||||
| Page Range: | pp. 263-297 | ||||
| DOI: | 10.1007/s00453-007-9032-7 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
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 |
