Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T06:59:03.863Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved approximation of the general soft-capacitated facility location problem

Published online by Cambridge University Press:  15 June 2007

Laurent Alfandari
Laurent Alfandari*
Affiliation:
ESSEC, BP 105 95021 Cergy-Pontoise, France, also LIPN, CNRS UMR-7030, Université Paris XIII, France; [email protected]
Get access

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.

Keywords

Facility locationset coveringdynamic programmingFPTAS.
Type
Research Article
Information
RAIRO - Operations Research , Volume 41 , Issue 1 , January 2007 , pp. 83 - 93
Copyright
© EDP Sciences, ROADEF, SMAI, 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
Feige, U., A threshold of lnn for approximating set cover. J. ACM 45 (1998) 634–652. 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.