skip to main content
column

Online and incremental algorithms for facility location

Published: 21 March 2011 Publication History

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.

Cited By

View all
  • (2024)Modeling Shifting Workloads for Learned Database SystemsProceedings of the ACM on Management of Data10.1145/36392932:1(1-27)Online publication date: 26-Mar-2024
  • (2024)Online Algorithmic Study of Facility Location Problems: A SurveyIEEE Access10.1109/ACCESS.2024.340678812(77724-77738)Online publication date: 2024
  • (2024)Solving the uncapacitated facility location problem under uncertainty: a hybrid tabu search with path-relinking simheuristic approachApplied Intelligence10.1007/s10489-024-05441-x54:7(5617-5638)Online publication date: 1-Apr-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM SIGACT News
ACM SIGACT News  Volume 42, Issue 1
March 2011
123 pages
ISSN:0163-5700
DOI:10.1145/1959045
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 March 2011
Published in SIGACT Volume 42, Issue 1

Check for updates

Qualifiers

  • Column

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)31
  • Downloads (Last 6 weeks)1
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Modeling Shifting Workloads for Learned Database SystemsProceedings of the ACM on Management of Data10.1145/36392932:1(1-27)Online publication date: 26-Mar-2024
  • (2024)Online Algorithmic Study of Facility Location Problems: A SurveyIEEE Access10.1109/ACCESS.2024.340678812(77724-77738)Online publication date: 2024
  • (2024)Solving the uncapacitated facility location problem under uncertainty: a hybrid tabu search with path-relinking simheuristic approachApplied Intelligence10.1007/s10489-024-05441-x54:7(5617-5638)Online publication date: 1-Apr-2024
  • (2024)Revisit the Online Facility Location Problem with Uniform Facility CostAlgorithmic Aspects in Information and Management10.1007/978-981-97-7798-3_12(133-144)Online publication date: 21-Sep-2024
  • (2023)An incremental facility location clustering with a new hybrid constrained pseudometricPattern Recognition10.1016/j.patcog.2023.109520141(109520)Online publication date: Sep-2023
  • (2023)Toward Online Mobile Facility Location on General MetricsTheory of Computing Systems10.1007/s00224-023-10145-967:6(1268-1306)Online publication date: 1-Dec-2023
  • (2023)Online Facility Location Problems Inspired by the COVID-19 PandemicInnovative Intelligent Industrial Production and Logistics10.1007/978-3-031-37228-5_7(110-123)Online publication date: 7-Jul-2023
  • (2022)Online facility location with mobile facilitiesTheoretical Computer Science10.1016/j.tcs.2022.01.019907:C(45-61)Online publication date: 12-Mar-2022
  • (2022)Algorithmic Study of Online Multi-Facility Location ProblemsSN Computer Science10.1007/s42979-022-01193-y3:4Online publication date: 19-May-2022
  • (2022)Facility Reallocation on the LineAlgorithmica10.1007/s00453-022-00993-184:10(2898-2925)Online publication date: 1-Oct-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media