Improved approximation of the general soft-capacitated facility location problem

Alfandari, Laurent

RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 1, pp. 83-93.

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\left(n\right)$ 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\left(n\right)$ for this problem.

Classification : 90B80, 90C59, 90C27
Mots clés : facility location, set covering, dynamic programming, FPTAS

[1] L. Alfandari and V. Paschos, Master-slave strategy and polynomial approximation. Comp. Opt. Appl. 16 (2000) 231-245. | Zbl

[2] A. Billionnet, Approximation algorithms for fractional knapsack problems. Op. Res. Lett. 30 (2002) 336-342.

[3] 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. | Zbl

[4] V. Chvátal, A greedy-heuristic for the set covering problem. Math. Oper. Res. 4 (1979) 233-235. | Zbl

[5] U. Feige, A threshold of $lnn$ for approximating set cover. J. ACM 45 (1998) 634-652. | Zbl

[6] M.R. Garey and D.S. Johnson,Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman, San Francisco (1979). | MR | Zbl

[7] N. Garg, R. Khandekar and V. Pandit, Improved approximation for universal facility location, in Proc. of SODA (2005) 959-960.

[8] R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Op. Res. 17 (1992) 36-42. | Zbl

[9] D.S. Hochbaum, Heuristics for the fixed cost median problem. Math. Prog. 22 (1982) 148-162. | Zbl

[10] O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problem. J. ACM 22 (1975) 463-468. | Zbl

[11] 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.

[12] 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.

[13] 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. ACM 50 (2003) 795-824.

[14] 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.

[15] E.L. Lawler, Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4 (1979) 339-356. | Zbl

[16] 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. | Zbl

[17] 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.

[18] 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. | Zbl

[19] J. Zhang, B. Chen and Y. Ye, Multi-exchange local search algorithm for capacitated facility location problem, in Proc. IPCO (2004) 219-233. | Zbl