An ex-post bound on the greedy heuristic for the uncapacitated facility location problem

Jean-Michel Thizy

RAIRO - Operations Research (2006)

  • Volume: 40, Issue: 2, page 143-167
  • ISSN: 0399-0559

Abstract

top
A bound for the greedy heuristic applied to the K-facility location problem can be calculated, using values gathered during the calculation of the heuristic. The bound strengthens a well-known bound for the heuristic. Computational experiments show that this bound can be beneficial when the number of facilities is small or close to the total number of potential sites. In addition, it is consistent with previous results about the influence of the data characteristics upon the optimal value.

How to cite

top

Thizy, Jean-Michel. "An ex-post bound on the greedy heuristic for the uncapacitated facility location problem." RAIRO - Operations Research 40.2 (2006): 143-167. <http://eudml.org/doc/249769>.

@article{Thizy2006,
abstract = { A bound for the greedy heuristic applied to the K-facility location problem can be calculated, using values gathered during the calculation of the heuristic. The bound strengthens a well-known bound for the heuristic. Computational experiments show that this bound can be beneficial when the number of facilities is small or close to the total number of potential sites. In addition, it is consistent with previous results about the influence of the data characteristics upon the optimal value. },
author = {Thizy, Jean-Michel},
journal = {RAIRO - Operations Research},
keywords = {facility location problem; greedy heuristic; bound},
language = {eng},
month = {10},
number = {2},
pages = {143-167},
publisher = {EDP Sciences},
title = {An ex-post bound on the greedy heuristic for the uncapacitated facility location problem},
url = {http://eudml.org/doc/249769},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Thizy, Jean-Michel
TI - An ex-post bound on the greedy heuristic for the uncapacitated facility location problem
JO - RAIRO - Operations Research
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 2
SP - 143
EP - 167
AB - A bound for the greedy heuristic applied to the K-facility location problem can be calculated, using values gathered during the calculation of the heuristic. The bound strengthens a well-known bound for the heuristic. Computational experiments show that this bound can be beneficial when the number of facilities is small or close to the total number of potential sites. In addition, it is consistent with previous results about the influence of the data characteristics upon the optimal value.
LA - eng
KW - facility location problem; greedy heuristic; bound
UR - http://eudml.org/doc/249769
ER -

References

top
  1. S. Ahn, C. Cooper, G. Cornuéjols and A. Frieze, Probabilistic Analysis of a Relaxation for the k-Median Problem. Math. Oper. Res.13 (1988) 1–31.  
  2. V. Chvátal, A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res.4 (1979) 233–235.  
  3. G. Cornuéjols, M.L. Fisher and G.L. Nemhauser, On the Uncapacitated Location Problem. Ann. Discrete Math.1 (1977) 163–178.  
  4. G. Cornuéjols, M.L. Fisher and G.L. Nemhauser, Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Science23 (1977) 789–810.  
  5. G. Cornuéjols, M.L. Fisher and G.L. Nemhauser Note on Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Science25 (1979) 808–809.  
  6. G. Cornuéjols and J.-M. Thizy, Location Problems, Set Covering Problems and the Greedy Algorithm, Working paper 25-80-81, Graduate School of Industrial Administration, Carnegie-Mellon University (April 1981), also available as Working Paper 02-51, School of Management, University of Ottawa (2002).  
  7. G. Cornuéjols and J.-M. Thizy, New Results on the Greedy Algorithm for Plant Location and Set Covering Problems, presented at the CORS-TIMS-ORSA Joint National Meeting, Toronto, Ontario, May 4, 1981.  
  8. G. Cornuéjols and J.-M. Thizy, A Primal Approach to the Simple Plant Location Problem. SIAM J. Algebraic Discrete Methods3 (1982) 504–510.  
  9. G. Cornuéjols, G.L. Nemhauser and L.A. Wolsey, The Uncapacitated Facility Location Problem, in: Discrete Location Theory, P.B. Mirchandani and R.M. Francis Eds., John Wiley and Sons, New–York (1990) 119–171.  
  10. A.M. El-Shaieb, A New Algorithm for Locating Sources Among Destinations. Management Science20 (1973) 221–231.  
  11. D. Erlenkotter, A Dual-based Procedure for Uncapacitated Facility Location. Oper. Res.26 (1978) 992–1009.  
  12. S. Even, Graph Algorithms. Computer Science Press, Potomac, Maryland (1979).  
  13. M.L. Fisher, G.L. Nemhauser and L.A. Wolsey, An Analysis of Approximations for Maximizing Submodular Set Functions-II, Mathematical Programming Study8 (1978) 73–87.  
  14. M.L. Fisher and L.A. Wolsey, On the Greedy Heuristic for Covering and Packing Problems, SIAM J. Algebraic Discrete Methods3 (1982) 584–591.  
  15. M. Guignard and K. Spielberg, Algorithms for exploiting the Structure of the Simple Plant Location Problem. Ann. Discrete Math.1 (1977) 247–271.  
  16. D.S. Johnson, Approximation Algorithms for Combinatorial Problems. J. Comput. System Sci.9 (1974) 256-298.  
  17. R.L. Karg and G.L. Thompson, A Heuristic Approach to Solving Traveling Salesman problems, Management Sci.10 (1964) 225–248.  
  18. P. Krolak, W. Felts and G. Marble, A Man-Machine Approach toward Solving the Traveling Salesman Problem. Communications of the Association for Computing Machinery14 (1971), 327–334.  
  19. A.A. Kuehn and M.J. Hamburger, A Heuristic Program for Locating Warehouses, Management Sci.9 (1963) 643–666.  
  20. G.L. Nemhauser, L.A. Wolsey and M.L. Fisher, An Analysis of Approximations for Maximizing Submodular Set Functions-I. Math. Program.14 (1978) 265–294.  
  21. L. Schrage, Implicit Representation of Variable Upper Bounds in Linear Programming, Math. Program. Stud.4 (1975) 118–132.  
  22. H.P. Simão and J.-M. Thizy, A Simplex Algorithm for the Canonical Representation of the Uncapacitated Plant Location Problem. Oper. Res. Lett.8 (1989) 279–286.  
  23. J.-M. Thizy, Location Problems: Properties and Algorithms, Ph.D. thesis, Graduate School of Industrial Administration, Carnegie Mellon University (1981).  
  24. J.-M. Thizy, Worst-case analysis of the uncapacitated facility location problem with a budget constraint, Working Paper, School of Management, University of Ottawa, to appear.  
  25. L.A. Wolsey, An analysis of the Greedy Algorithm for the Submodular Set Covering Problem'. Combinatorica2 (1982) 417–425.  

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.