Improved approximation of the general soft-capacitated facility location problem
RAIRO - Operations Research (2007)
- Volume: 41, Issue: 1, page 83-93
- ISSN: 0399-0559
Access Full Article
top
Abstract
topHow to cite
topAlfandari, Laurent. "Improved approximation of the general soft-capacitated facility location problem." RAIRO - Operations Research 41.1 (2007): 83-93. <http://eudml.org/doc/250108>.
@article{Alfandari2007,
abstract = {
The soft-capacitated facility location problem, where each facility is
composed of a variable number of fixed-capacity production units, has been recently studied in several papers,
especially in the metric case. In this paper, we only consider the
general problem where connection costs do not systematically satisfy the triangle inequality property.
We show that an adaptation of the set covering greedy heuristic,
where the subproblem is approximately solved by a fully polynomial-time approximation scheme based on cost scaling and
dynamic programming, achieves a logaritmic approximation ratio of (1 + ε)H(n) for the problem,
where n is the number of customers to be served and H is the harmonic series. This improves the previous bound of
2H(n) for this problem.
},
author = {Alfandari, Laurent},
journal = {RAIRO - Operations Research},
keywords = {Facility location; set covering; dynamic programming; FPTAS.},
language = {eng},
month = {6},
number = {1},
pages = {83-93},
publisher = {EDP Sciences},
title = {Improved approximation of the general soft-capacitated facility location problem},
url = {http://eudml.org/doc/250108},
volume = {41},
year = {2007},
}
TY - JOUR
AU - Alfandari, Laurent
TI - Improved approximation of the general soft-capacitated facility location problem
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 1
SP - 83
EP - 93
AB -
The soft-capacitated facility location problem, where each facility is
composed of a variable number of fixed-capacity production units, has been recently studied in several papers,
especially in the metric case. In this paper, we only consider the
general problem where connection costs do not systematically satisfy the triangle inequality property.
We show that an adaptation of the set covering greedy heuristic,
where the subproblem is approximately solved by a fully polynomial-time approximation scheme based on cost scaling and
dynamic programming, achieves a logaritmic approximation ratio of (1 + ε)H(n) for the problem,
where n is the number of customers to be served and H is the harmonic series. This improves the previous bound of
2H(n) for this problem.
LA - eng
KW - Facility location; set covering; dynamic programming; FPTAS.
UR - http://eudml.org/doc/250108
ER -
References
top- L. Alfandari and V. Paschos, Master-slave strategy and polynomial approximation. Comp. Opt. Appl.16 (2000) 231–245.
- A. Billionnet, Approximation algorithms for fractional knapsack problems. Op. Res. Lett.30 (2002) 336–342.
- F.A. Chudak and D.P. Williamson, Improved approximation algorithms for capacitated facility location problems, in Proc. of the 7th IFCO Conference (1999) 99–113.
- V. Chvátal, A greedy-heuristic for the set covering problem. Math. Oper. Res.4 (1979) 233–235.
- U. Feige, A threshold of lnn for approximating set cover. J. ACM45 (1998) 634–652.
- M.R. Garey and D.S. Johnson,Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman, San Francisco (1979).
- N. Garg, R. Khandekar and V. Pandit, Improved approximation for universal facility location, in Proc. of SODA (2005) 959–960.
- R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Op. Res.17 (1992) 36–42.
- D.S. Hochbaum, Heuristics for the fixed cost median problem. Math. Prog.22 (1982) 148–162.
- O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problem. J. ACM22 (1975) 463–468.
- K. Jain and V.V. Vazirani, Primal-dual approximation algorithms for metric facility location and k-median problems, in Proc. of the 40th Annual IEEE Symp. on Foundations of Comp. Sc. (1999) 2–13.
- K. Jain, M. Mahdian and A. Saberi, A new greedy approach for facility location problems, in Proc. of the 34st Annual ACM Symp. on Th. of Computing (2002) 731–740.
- K. Jain, M. Mahdian, E. Markakis, A. Saberi and V.V. Vazirani, Greedy facility location algorithms analysed using dual fitting with factor-revealing LP. J. ACM50 (2003) 795–824.
- R.M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations, edited by R.E. Miller and J.W. Thatche, Plenum Press, NY (1972) 85–103.
- E.L. Lawler, Fast approximation algorithms for knapsack problems. Math. Oper. Res.4 (1979) 339–356.
- M. Mahdian, Y. Ye and J. Zhang, Improved approximation algorithm for metric facility location problems, in Proc. of the 5th Intl Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002) (2002) 229–242.
- M. Mahdian, Y. Ye and J. Zhang. A 2-approximation algorithm for the soft-capacitated facility location problem, in Proc. of the 6th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization (2003) 129–140.
- D.B. Shmoys, E. Tardos and K. Aardal. Approximation algorithms for facility location problems, in Proc. 29th Annual ACM Symp. on Th. Computing (1997) 265–274.
- J. Zhang, B. Chen and Y. Ye, Multi-exchange local search algorithm for capacitated facility location problem, in Proc. IPCO (2004) 219–233.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.