Approximation algorithms for soft-capacitated facility location in capacitated network design
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-4617Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-007-9032-7
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|
|Number of Pages:||35|
|Page Range:||pp. 263-297|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)