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.
@article{RO_2006__40_2_143_0,
author = {Thizy, Jean-Michel},
title = {An ex-post bound on the greedy heuristic for the uncapacitated facility location problem},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {143--167},
publisher = {EDP-Sciences},
volume = {40},
number = {2},
year = {2006},
doi = {10.1051/ro:2006016},
mrnumber = {2272684},
zbl = {1115.90033},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2006016/}
}
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 - Recherche Opérationnelle PY - 2006 SP - 143 EP - 167 VL - 40 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2006016/ DO - 10.1051/ro:2006016 LA - en ID - RO_2006__40_2_143_0 ER -
%0 Journal Article %A Thizy, Jean-Michel %T An ex-post bound on the greedy heuristic for the uncapacitated facility location problem %J RAIRO - Operations Research - Recherche Opérationnelle %D 2006 %P 143-167 %V 40 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2006016/ %R 10.1051/ro:2006016 %G en %F RO_2006__40_2_143_0
Thizy, Jean-Michel. An ex-post bound on the greedy heuristic for the uncapacitated facility location problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 40 (2006) no. 2, pp. 143-167. doi : 10.1051/ro:2006016. http://www.numdam.org/articles/10.1051/ro:2006016/
[1] ,, and, Probabilistic Analysis of a Relaxation for the k-Median Problem. Math. Oper. Res. 13 (1988) 1-31. | Zbl
[2] , A Greedy Heuristic for the Set-Covering Problem. Math. Oper. Res. 4 (1979) 233-235. | Zbl
[3] , and, On the Uncapacitated Location Problem. Ann. Discrete Math. 1 (1977) 163-178. | Zbl
[4] , and, Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Science 23 (1977) 789-810. | Zbl
[5] , and on Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms. Management Science 25 (1979) 808-809. | Zbl
[6] and, 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] and, 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] and, A Primal Approach to the Simple Plant Location Problem. SIAM J. Algebraic Discrete Methods 3 (1982) 504-510. | Zbl
[9] , and, 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. | Zbl
[10] , A New Algorithm for Locating Sources Among Destinations. Management Science 20 (1973) 221-231. | Zbl
[11] , A Dual-based Procedure for Uncapacitated Facility Location. Oper. Res. 26 (1978) 992-1009. | Zbl
[12] , Graph Algorithms. Computer Science Press, Potomac, Maryland (1979). | MR | Zbl
[13] , and, An Analysis of Approximations for Maximizing Submodular Set Functions-II, Mathematical Programming Study 8 (1978) 73-87. | MR | Zbl
[14] and, On the Greedy Heuristic for Covering and Packing Problems, SIAM J. Algebraic Discrete Methods 3 (1982) 584-591. | MR | Zbl
[15] and, Algorithms for exploiting the Structure of the Simple Plant Location Problem. Ann. Discrete Math. 1 (1977) 247-271. | MR | Zbl
[16] , Approximation Algorithms for Combinatorial Problems. J. Comput. System Sci. 9 (1974) 256-298. | MR | Zbl
[17] and, A Heuristic Approach to Solving Traveling Salesman problems, Management Sci. 10 (1964) 225-248.
[18] , and, A Man-Machine Approach toward Solving the Traveling Salesman Problem. Communications of the Association for Computing Machinery 14 (1971), 327-334. | Zbl
[19] and, A Heuristic Program for Locating Warehouses, Management Sci. 9 (1963) 643-666.
[20] , and, An Analysis of Approximations for Maximizing Submodular Set Functions-I. Math. Program. 14 (1978) 265-294. | MR | Zbl
[21] , Implicit Representation of Variable Upper Bounds in Linear Programming, Math. Program. Stud. 4 (1975) 118-132. | MR | Zbl
[22] and, A Simplex Algorithm for the Canonical Representation of the Uncapacitated Plant Location Problem. Oper. Res. Lett. 8 (1989) 279-286. | MR
[23] , Location Problems: Properties and Algorithms, Ph.D. thesis, Graduate School of Industrial Administration, Carnegie Mellon University (1981).
[24] , Worst-case analysis of the uncapacitated facility location problem with a budget constraint, Working Paper, School of Management, University of Ottawa, to appear.
[25] , An analysis of the Greedy Algorithm for the Submodular Set Covering Problem'. Combinatorica 2 (1982) 417-425. | Zbl
Cité par Sources :
