Online and incremental algorithms for facility location

Abstract

In the online and incremental variants of Facility Location, the demands arrive one-by-one and must be assigned to an open facility upon arrival, without any knowledge about future demands. In the online variant, the decisions of opening a facility at a particular location and of assigning a demand to some facility are irrevocable. In the incremental variant, the algorithm can also merge existing facilities (and the corresponding demand clusters) with each other, and only the decision of assigning some demands to the same facility is irrevocable. The goal is to maintain, either online or incrementally, a set of facilities and an assignment of the demands to them that minimize the total facility opening cost plus the assignment cost for all demands.

In this survey, we discuss the previous work on online and incremental algorithms for Facility Location. In addition to the main results, namely that the competitive ratio for the online variant is Θ(log nlog log n), where n is the number of demands, and that the competitive ratio for the incremental variant is O(1), we discuss all known online and incremental Facility Location algorithms, sketch the intuition behind them and the main ideas of their competitive analysis, and discuss some applications.

References

1. N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. A General Approach to Online Network Optimization Problems. ACM Transactions on Algorithms, 2(4):640--660, 2006.
2. N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, and J. Naor. The Online Set Cover Problem. SIAM J. on Computing, 39(2):361--370, 2009.
3. A. Anagnostopoulos, R. Bent, E. Upfal, and P. Van Hentenryck. A Simple and Deterministic Competitive Algorithm for Online Facility Location. Information and Computation, 194:175--202, 2004.
4. B.M. Anthony and A. Gupta. Infrastructure Leasing Problems. In Proc. of the 12th Conference on Integer Programming and Combinatorial Optimization (IPCO '07), volume 4513 of LNCS, pages 424--438, 2007.
5. V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local Search Heuristics for k-Median and Facility Location Problems. SIAM J. on Computing, 33(3):544--562, 2004.
6. A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
7. J. Byrka and K. Aardal. An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. SIAM J. on Computing, 39(6):2212--2231, 2010.
8. M. Charikar, C. Chekuri, T. Feder, and R. Motwani. Incremental Clustering and Dynamic Information Retrieval. In Proc. of the 29th ACM Symposium on Theory of Computing (STOC '97), pages 626--635, 1997.
9. M. Charikar and S. Guha. Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. on Computing, 34(4):803--824, 2005.
10. M. Charikar, L. O'Callaghan, and R. Panigrahy. Better Streaming Algorithms for Clustering Problems. In Proc. of the 35th ACM Symposium on Theory of Computing (STOC '03), pages 30--39, 2003.
11. M. Charikar and R. Panigrahy. Clustering to Minimize the Sum of Cluster Diameters. In Proc. of the 33rd ACM Symposium on Theory of Computing (STOC '01), pages 1--10, 2001.
12. M. Chrobak and C. Kenyon-Mathieu. Online Algorithms Column 10: Competitiveness via Doubling. SIGACT News, 37(4):115--126, 2006.
13. G. Divéki and C. Imreh. Online Facility Location with Facility Movements. Central European Journal of Operations Research, 2010.
14. Z. Drezner and H.W. Hamacher (Editors). Facility Location: Applications and Theory. Springer, 2004.
15. J. Fakcharoenphol, S. Rao, and K. Talwar. Approximating Metric Spaces by Tree Metrics. Encyclopedia of Algorithms, pages 51--53, 2008.
16. D. Fotakis. Incremental Algorithms for Facility Location and k-Median. Theoretical Computer Science, 361(2-3):275--313, 2006.
17. D. Fotakis. Memoryless Facility Location in One Pass. In Proc. of the 23st Symposium on Theoretical Aspects of Computer Science (STACS '06), volume 3884 of LNCS, pages 608--620, 2006.
18. D. Fotakis. A Primal-Dual Algorithm for Online Non-Uniform Facility Location. Journal of Discrete Algorithms, 5(1):141--148, 2007.
19. D. Fotakis. On the Competitive Ratio for Online Facility Location. Algorithmica, 50(1):1--57, 2008.
20. D. Fotakis and C. Tzamos. Winner-Imposing Strategyproof Mechanisms for Multiple Facility Location Games. In Proc. of the 6th Workshop on Internet and Network Economics (WINE '10), volume 6484 of LNCS, pages 234--245, 2010.
21. G. Frahling and C. Sohler. Coresets in Dynamic Geometric Data Streams. In Proc. of the 37th ACM Symposium on Theory of Computing (STOC '05), pages 209--217, 2005.
22. S. Guha and S. Khuller. Greedy Strikes Back: Improved Facility Location Algorithms. Journal of Algorithms, 31(1):228--248, 1999.
23. S. Guha, A. Meyerson, N. Mishra, R. Motwani, and L. O'Callaghan. Clustering Data Streams: Theory and Practice. IEEE Transactions on Knowledge and Data Engineering, 15(3):515--528, 2003.
24. S. Guha, N. Mishra, R. Motwani, and L. O'Callaghan. Clustering Data Streams. In Proc. of the 41st IEEE Symposium on Foundations of Computer Science (FOCS '00), pages 359--366, 2000.
25. P. Indyk. Algorithms for Dynamic Geometric Problems over Data Streams. In Proc. of the 36th ACM Symposium on Theory of Computing (STOC '04), pages 373--380, 2004.
26. K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani. Greedy Facility Location Algorithms Analyzed Using Dual Fitting with Factor-Revealing LP. J. of the Association for Computing Machinery, 50(6):795--824, 2003.
27. K. Jain and V. Vazirani. Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation. J. of the Association for Computing Machinery, 48(2):274--296, 2001.
28. C. Lammersen and C. Sohler. Facility Location in Dynamic Geometric Data Streams. In Proc. of the 16th European Symposium on Algorithms (ESA '08), volume 5193 of LNCS, pages 660--671, 2008.
29. P. Lu, X. Sun, Y.Wang, and Z.A. Zhu. Asymptotically Optimal Strategy-Proof Mechanisms for Two-Facility Games. In Proc. of the 11th ACM Conference on Electronic Commerce (EC '10), pages 315--324, 2010.
30. P. Lu, Y.Wang, and Y. Zhou. Tighter Bounds for Facility Games. In Proc. of the 5th Workshop on Internet and Network Economics (WINE '09), volume 5929 of LNCS, pages 137--148, 2009.
31. M. Mahdian, Y. Ye, and J. Zhang. Improved Approximation Algorithms for Metric Facility Location Problems. In Proc. of the 5th Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX '02), volume 2462 of LNCS, pages 229--242, 2002.
32. R.R. Mettu and C.G. Plaxton. The Online Median Problem. SIAM J. on Computing, 32(3):816--832, 2003.
33. A. Meyerson. Online Facility Location. In Proc. of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS '01), pages 426--431, 2001.
34. A. Meyerson. The Parking Permit Problem. In Proc. of the 46th IEEE Symposium on Foundations of Computer Science (FOCS '05), pages 274--284, 2005.
35. C. Nagarajan and D.P. Williamson. Offine and Online Facility Leasing. In Proc. of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO '08), volume 5035 of LNCS, pages 303--315, 2008.
36. R.L. Francis (Editors) P.B. Mirchandani. Discrete Location Theory. Willey, 1990.
37. A.D. Procaccia and M. Tennenholtz. Approximate Mechanism Design Without Money. In Proc. of the 10th ACM Conference on Electronic Commerce (EC '09), pages 177--186, 2009.
38. J. Schummer and R.V. Vohra. Strategyproof Location on a Network. Journal of Economic Theory, 104:405--428, 2002.
39. D. Shmoys. Approximation Algorithms for Facility Location Problems. In Proc. of the 3rd Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX '00), volume 1913 of LNCS, pages 27--33, 2000.
40. D. Shmoys, E. Tardos, and K. Aardal. Approximation Algorithms for Facility Location Problems. In Proc. of the 29th ACM Symposium on Theory of Computing (STOC '97), pages 265--274, 1997.
41. M. Sviridenko. An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem. In Proc. of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO '02), volume 2337 of LNCS, pages 240--257, 2002.
42. M. Thorup. Quick k-Median, k-Center, and Facility Location for Sparse Graphs. SIAM J. on Computing, 34(2):405--432, 2005.

Index Terms

• General and reference

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

      • Online learning algorithms

  • Models of computation

    • Interactive computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory