No CrossRef data available.
Article contents
Improved approximation of the general soft-capacitated facility location problem
Published online by Cambridge University Press: 15 June 2007
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.
Information
- Type
- Research Article
- Information
- Copyright
- © EDP Sciences, ROADEF, SMAI, 2007
References
Alfandari, L. and Paschos, V., Master-slave strategy and polynomial approximation.
Comp. Opt. Appl.
16 (2000) 231–245.
CrossRef
Billionnet, A., Approximation algorithms for fractional knapsack problems.
Op. Res. Lett.
30 (2002) 336–342.
CrossRef
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.
Chvátal, V., A greedy-heuristic for the set covering problem.
Math. Oper. Res.
4 (1979) 233–235.
CrossRef
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.
Hassin, R., Approximation schemes for the restricted shortest path problem.
Math. Op. Res.
17 (1992) 36–42.
CrossRef
Hochbaum, D.S., Heuristics for the fixed cost median problem.
Math. Prog.
22 (1982) 148–162.
CrossRef
Ibarra, O.H. and Kim, C.E., Fast approximation algorithms for the knapsack and sum of subset problem.
J. ACM
22 (1975) 463–468.
CrossRef
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.
Jain, K., Mahdian, M., Markakis, E., Saberi, A. and Vazirani, V.V., Greedy facility location algorithms analysed using dual fitting with factor-revealing LP.
J. ACM
50 (2003) 795–824.
CrossRef
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.
Lawler, E.L., Fast approximation algorithms for knapsack problems.
Math. Oper. Res.
4 (1979) 339–356.
CrossRef
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.