×

A simple and deterministic competitive algorithm for online facility location. (English) Zbl 1089.90036

Summary: This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also applies to a variety of models, i.e., models where the facilities can be placed anywhere in the region, or only at customer sites, or only at fixed locations. The paper shows that the algorithm is \(O (\log n)\)-competitive under these various models, where \(n\) is the total number of customers. It also shows that the algorithm is \(O(1)\)-competitive with high probability and for any arrival order when customers are uniformly distributed or when they follow a distribution satisfying a smoothness property. Experimental results for a variety of scenarios indicate that the algorithm behaves extremely well in practice.

MSC:

90B80 Discrete location and assignment
68W40 Analysis of algorithms

Software:

COMET
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bentley, J. L., Multidimensional binary search trees used for associative searching, Commun. ACM, 18, 9, 509-517 (1975) · Zbl 0306.68061
[2] Buchsbaum, A.; Kanellakis, P.; Vitter, J., A data structure for arc insertion and regular path finding, Ann. Math. Artif. Intell., 3, 2-4, 187-211 (1991) · Zbl 0877.68032
[3] Chávez, E.; Navarro, G.; Baeza-Yates, R.; Marroquı́n, J. L., Searching in metric spaces, ACM Comput. Surv., 33, 3, 273-321 (2001)
[4] F.A. Chudak, D.B. Shmoys, Improved approximation algorithms for a capacitated facility location problem, in: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’99), ACM-SIAM, NY, 1999, pp. 875-876; F.A. Chudak, D.B. Shmoys, Improved approximation algorithms for a capacitated facility location problem, in: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’99), ACM-SIAM, NY, 1999, pp. 875-876 · Zbl 1052.90580
[5] G. Cornuéjols, G. Nemhauser, L. Wolsey, Discrete Location Theory, Lecture Note in Artificial Intelligence (LNAI 1865), Ch. The Uncapacitated Facility Location Problem, Wiley, 1990, pp. 119-171; G. Cornuéjols, G. Nemhauser, L. Wolsey, Discrete Location Theory, Lecture Note in Artificial Intelligence (LNAI 1865), Ch. The Uncapacitated Facility Location Problem, Wiley, 1990, pp. 119-171
[6] Erlenkotter, D., A dual-based procedure for uncapacitated facility location: general solution procedures and computational experience, Oper. Res., 26, 992-1009 (1978) · Zbl 0422.90053
[7] D. Fotakis, On the competitive ratio for online facility location, in: Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP ’03), 2003, pp. 637-652; D. Fotakis, On the competitive ratio for online facility location, in: Proceedings of the 13th International Colloquium on Automata, Languages and Programming (ICALP ’03), 2003, pp. 637-652 · Zbl 1039.68117
[8] Gao, L.; Robinson, E., Uncapacitated facility location: general solution procedures and computational experience, Eur. J. Oper. Res., 76, 410-427 (1994) · Zbl 0810.90085
[9] S. Guha, S. Khuller, Greedy strikes back: improved facility location algorithms, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’98), San Francisco, California, 1998, pp. 649-657; S. Guha, S. Khuller, Greedy strikes back: improved facility location algorithms, in: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’98), San Francisco, California, 1998, pp. 649-657 · Zbl 0936.68114
[10] Jain, K.; Vazirani, V. V., Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation, J. ACM, 48, 2, 274-296 (2001) · Zbl 1138.90417
[11] I. Karatzas, E. Protonotarios, P. Kanellakis, Easy-to-test criteria for weak stochastic stability of dynamical systems, in: John Hopkins Conference on Information Sciences and Systems, Baltimore, MD, 1978, p. 535; I. Karatzas, E. Protonotarios, P. Kanellakis, Easy-to-test criteria for weak stochastic stability of dynamical systems, in: John Hopkins Conference on Information Sciences and Systems, Baltimore, MD, 1978, p. 535
[12] D. Karger, M. Ruhl, Finding nearest neighbors in growth-restricted metrics, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC ’02), ACM Press, New York, 2002, pp. 741-750; D. Karger, M. Ruhl, Finding nearest neighbors in growth-restricted metrics, in: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC ’02), ACM Press, New York, 2002, pp. 741-750 · Zbl 1192.68750
[13] Kratica, J.; Tosic, D.; Filipovic, V.; Ljubic, I., Solving the simple plant location problemsby genetic algorithm, RAIRO Oper. Res., 35, 127-142 (2001) · Zbl 0995.90055
[14] M. Mahdian, Y. Ye, J. Zhang, Improved approximation algorithms for metric facility location problems, in: Proceedings of Fifth International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX ’02), vol. 2462 of Lecture Notes in Computer Science, 2002, pp. 229-242; M. Mahdian, Y. Ye, J. Zhang, Improved approximation algorithms for metric facility location problems, in: Proceedings of Fifth International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX ’02), vol. 2462 of Lecture Notes in Computer Science, 2002, pp. 229-242 · Zbl 1013.90115
[15] R.R. Mettu, C.G. Plaxton, The online median problem, in: IEEE (Ed.), Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS ’00), IEEE Computer Society Press, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 2000, pp. 339-348; R.R. Mettu, C.G. Plaxton, The online median problem, in: IEEE (Ed.), Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS ’00), IEEE Computer Society Press, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 2000, pp. 339-348 · Zbl 1128.90550
[16] A. Meyerson, Online facility location, in: IEEE (Ed.), 42nd IEEE Symposium on Foundations of Computer Science: Proceedings: October 14-17, 2001, Las Vegas, Nevada, USA, IEEE Computer Society Press, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 2001, pp. 426-431; A. Meyerson, Online facility location, in: IEEE (Ed.), 42nd IEEE Symposium on Foundations of Computer Science: Proceedings: October 14-17, 2001, Las Vegas, Nevada, USA, IEEE Computer Society Press, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 2001, pp. 426-431
[17] L. Michel, P. Van Hentenryck, A constraint-based architecture for local search, in: OOPLSA’02, Seattle, WA, 2002; L. Michel, P. Van Hentenryck, A constraint-based architecture for local search, in: OOPLSA’02, Seattle, WA, 2002
[18] L. Michel, P. Van Hentenryck, A simple tabu-search algorithm for warehouse location, Eur. J. Oper. Res., to appear; L. Michel, P. Van Hentenryck, A simple tabu-search algorithm for warehouse location, Eur. J. Oper. Res., to appear · Zbl 1067.90054
[19] L. Michel, P. Van Hentenryck, Comet in context, in: Principles of Computing and Knowledge (PCK’50), San Diego, CA, 2003; L. Michel, P. Van Hentenryck, Comet in context, in: Principles of Computing and Knowledge (PCK’50), San Diego, CA, 2003
[20] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge, England · Zbl 0849.68039
[21] D. Shmoys, Approximation algorithms for facility location problems, in: Proceedings of Third International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX ’00), vol. 1913 of Lecture Notes in Computer Science, 2000, pp. 27-33; D. Shmoys, Approximation algorithms for facility location problems, in: Proceedings of Third International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX ’00), vol. 1913 of Lecture Notes in Computer Science, 2000, pp. 27-33 · Zbl 0976.68538
[22] D.B. Shmoys, É. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC ’97), Association for Computing Machinery, New York, 1997, pp. 265-274; D.B. Shmoys, É. Tardos, K. Aardal, Approximation algorithms for facility location problems, in: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC ’97), Association for Computing Machinery, New York, 1997, pp. 265-274 · Zbl 0962.68008
[23] Sleator, D.; Tarjan, R., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 202-208 (1985)
[24] United States Census Bureau, Year 2000 Population Estimates. Available from: <http://www.census.gov/; United States Census Bureau, Year 2000 Population Estimates. Available from: <http://www.census.gov/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.