Improved approximation of the general soft-capacitated facility location problem

Laurent Alfandari

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 1, page 83-93
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Alfandari, 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
  1. L. Alfandari and V. Paschos, Master-slave strategy and polynomial approximation. Comp. Opt. Appl.16 (2000) 231–245.  Zbl1017.90081
  2. A. Billionnet, Approximation algorithms for fractional knapsack problems. Op. Res. Lett.30 (2002) 336–342.  Zbl1146.90498
  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.  Zbl0955.90068
  4. V. Chvátal, A greedy-heuristic for the set covering problem. Math. Oper. Res.4 (1979) 233–235.  Zbl0443.90066
  5. U. Feige, A threshold of lnn for approximating set cover. J. ACM45 (1998) 634–652.  Zbl1065.68573
  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).  Zbl0411.68039
  7. N. Garg, R. Khandekar and V. Pandit, Improved approximation for universal facility location, in Proc. of SODA (2005) 959–960.  Zbl1297.90070
  8. R. Hassin, Approximation schemes for the restricted shortest path problem. Math. Op. Res.17 (1992) 36–42.  Zbl0763.90083
  9. D.S. Hochbaum, Heuristics for the fixed cost median problem. Math. Prog.22 (1982) 148–162.  Zbl0473.90029
  10. O.H. Ibarra and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problem. J. ACM22 (1975) 463–468.  Zbl0345.90049
  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.  Zbl1192.90106
  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. ACM50 (2003) 795–824.  Zbl1325.90060
  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.  Zbl0425.90064
  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.  Zbl1013.90115
  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.  Zbl1279.68358
  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.  Zbl0962.68008
  19. J. Zhang, B. Chen and Y. Ye, Multi-exchange local search algorithm for capacitated facility location problem, in Proc. IPCO (2004) 219–233.  Zbl1092.90525

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.