A simple and deterministic competitive algorithm for online facility location
Tóm tắt
Từ khóa
Tài liệu tham khảo
Bentley, 1975, Multidimensional binary search trees used for associative searching, Commun. ACM, 18, 509, 10.1145/361002.361007
Buchsbaum, 1991, A data structure for arc insertion and regular path finding, Ann. Math. Artif. Intell., 3, 187, 10.1007/BF01530925
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
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
Erlenkotter, 1978, A dual-based procedure for uncapacitated facility location: general solution procedures and computational experience, Oper. Res., 26, 992, 10.1287/opre.26.6.992
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
Gao, 1994, Uncapacitated facility location: general solution procedures and computational experience, Eur. J. Oper. Res., 76, 410, 10.1016/0377-2217(94)90277-1
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
Jain, 2001, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation, J. ACM, 48, 274, 10.1145/375827.375845
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
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
Kratica, 2001, Solving the simple plant location problemsby genetic algorithm, RAIRO Oper. Res., 35, 127, 10.1051/ro:2001107
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
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
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
L. Michel, P. Van Hentenryck, A constraint-based architecture for local search, in: OOPLSA’02, Seattle, WA, 2002
L. Michel, P. Van Hentenryck, A simple tabu-search algorithm for warehouse location, Eur. J. Oper. Res., to appear
L. Michel, P. Van Hentenryck, Comet in context, in: Principles of Computing and Knowledge (PCK’50), San Diego, CA, 2003
Motwani, 1995
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.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
Sleator, 1985, Amortized efficiency of list update and paging rules, Commun. ACM, 28, 202, 10.1145/2786.2793
United States Census Bureau, Year 2000 Population Estimates. Available from: <http://www.census.gov/>