Document Open Access Logo

Online Facility Location with Deletions

Authors Marek Cygan, Artur Czumaj, Marcin Mucha, Piotr Sankowski

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.21.pdf
  • Filesize: 444 kB
  • 15 pages

Document Identifiers

Author Details

Marek Cygan
  • Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland
Artur Czumaj
  • Department of Computer Science and Centre for Discrete Mathematics and its Applications (DIMAP), University of Warwick, Coventry CV4 7AL, United Kingdom
Marcin Mucha
  • Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland
Piotr Sankowski
  • Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

Funding

Research partially supported by the Royal Society International Exchanges Scheme 2013/R1, grant IE130346, by the Centre for Discrete Mathematics and its Applications (DIMAP), by EPSRC awards EP/D063191/1, EP/N011163/1, and by the European Research Council research and innovation programme (ERC grant agreement No 677651).

Cite AsGet BibTex

Marek Cygan, Artur Czumaj, Marcin Mucha, and Piotr Sankowski. Online Facility Location with Deletions. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.21

Abstract

In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only allowed to arrive to the system, but they can also depart at any moment. We begin with the study of a natural fully-dynamic online uncapacitated model where clients can be both added and removed. When a client arrives, then it has to be assigned either to an existing facility or to a new facility opened at the client's location. However, when a client who has been also one of the open facilities is to be removed, then our model has to allow to reconnect all clients that have been connected to that removed facility. In this model, we present an optimal O(log(n_{act}) / log log(n_{act}))-competitive algorithm, where n_{act} is the number of active clients at the end of the input sequence. Next, we turn our attention to the capacitated Facility Location problem. We first note that if no deletions are allowed, then one can achieve an optimal competitive ratio of O(log(n) / log(log n)), where n is the length of the sequence. However, when deletions are allowed, the capacitated version of the problem is significantly more challenging than the uncapacitated one. We show that still, using a more sophisticated algorithmic approach, one can obtain an online O(log N + log c log n)-competitive algorithm for the capacitated Facility Location problem in the fully dynamic model, where N is number of points in the input metric and c is the capacity of any open facility.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • online algorithms
  • facility location
  • fully-dynamic online algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2012), pages 459-467. Society for Industrial and Applied Mathematics, 2012. Google Scholar
  2. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. In Proceedings of the 17th International Workshop on Approximation, Randomization, and Combinatorial Optimization (RANDOM'2013), pages 1-10. Springer Verlag, Berlin, Heidelberg, 2013. Google Scholar
  3. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, and Joseph (Seffi) Naor. A general approach to online network optimization problems. ACM Transactions on Algorithms, 2(4):640-660, 2006. URL: http://dx.doi.org/10.1145/1198513.1198522.
  4. Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Transactions on Algorithms, 13(2):21:1-21:20, 2017. URL: http://dx.doi.org/10.1145/2928272.
  5. Hyung-Chan An, Mohit Singh, and Ola Svensson. LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1):272-306, 2017. URL: http://dx.doi.org/10.1137/151002320.
  6. Aris Anagnostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck. A simple and deterministic competitive algorithm for online facility location. Information and Computation, 194(2):175-202, 2004. URL: http://dx.doi.org/10.1016/j.ic.2004.06.002.
  7. Aris Anagnostopoulos, Fabrizio Grandoni, Stefano Leonardi, and Piotr Sankowski. Online network design with outliers. Algorithmica, 76(1):88-109, 2016. URL: http://dx.doi.org/10.1007/s00453-015-0021-y.
  8. Mihai Badoiu, Artur Czumaj, Piotr Indyk, and Christian Sohler. Facility location in sublinear time. In Proceedings of the 32nd Annual International Colloquium on Automata, Languages and Programming (ICALP'2005), volume 3580 of Lecture Notes in Computer Science, pages 866-877. Springer Verlag, Berlin, Heidelberg, 2005. URL: http://dx.doi.org/10.1007/11523468_70.
  9. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, (FOCS'1996), pages 184-193. IEEE Computer Society, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548477.
  10. Yair Bartal. On approximating arbitrary metrices by tree metrics. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC'1998), pages 161-168. ACM Press, 1998. URL: http://dx.doi.org/10.1145/276698.276725.
  11. Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998. Google Scholar
  12. Jaroslaw Byrka and Karen Aardal. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM Journal on Computing, 39(6):2212-2231, 2010. URL: http://dx.doi.org/10.1137/070708901.
  13. Graham Cormode and S. Muthukrishnan. Space efficient mining of multigraph streams. In Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS'2005), pages 271-282. ACM, 2005. URL: http://dx.doi.org/10.1145/1065167.1065201.
  14. Gérard Cornuéjols, George L. Nemhauser, and Lairemce A. Wolsey. The uncapacitated facility location problem. In Pitu B. Mirchandani and Richard L. Francis, editors, Discrete Location Theory, pages 119-171. John Wiley and Son, Inc., New York, 1990. Google Scholar
  15. Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, and Christian Sohler. (1 + ε)-approximation for facility location in data streams. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2013), pages 1710-1728. Society for Industrial and Applied Mathematics, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.123.
  16. Wenqiang Dai and Xianju Zeng. Incremental facility location problem and its competitive algorithms. Journal of Combinatorial Optimization, 20(3):307-320, 2010. URL: http://dx.doi.org/10.1007/s10878-009-9219-8.
  17. Gabriella Divéki and Csanád Imreh. Online facility location with facility movements. Central European Journal of Operations Research, 19(2):191-200, June 2011. URL: http://dx.doi.org/10.1007/s10100-010-0153-8.
  18. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 69(3):485-497, November 2004. URL: http://dx.doi.org/10.1016/j.jcss.2004.04.011.
  19. Ian Foster and Carl Kesselman, editors. The Grid: Blueprint for a New Computing Infrastructure. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1999. Google Scholar
  20. Dimitris Fotakis. Incremental algorithms for facility location and k-median. Theoretical Computer Science, 361(2-3):275-313, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.05.015.
  21. Dimitris Fotakis. A primal-dual algorithm for online non-uniform facility location. Journal of Discrete Algorithms, 5(1):141-148, 2007. URL: http://dx.doi.org/10.1016/j.jda.2006.03.001.
  22. Dimitris Fotakis. On the competitive ratio for online facility location. Algorithmica, 50(1):1-57, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9049-y.
  23. Dimitris Fotakis. Online and incremental algorithms for facility location. SIGACT News, 42(1):97-131, 2011. Google Scholar
  24. Gereon Frahling and Christian Sohler. Coresets in dynamic geometric data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC'2005), pages 209-217. ACM Press, 2005. URL: http://dx.doi.org/10.1145/1060590.1060622.
  25. Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2008), pages 942-951. Society for Industrial and Applied Mathematics, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347185.
  26. Fabrizio Grandoni, Anupam Gupta, Stefano Leonardi, Pauli Miettinen, Piotr Sankowski, and Mohit Singh. Set covering with our eyes closed. SIAM Journal on Computing, 42(3):808-830, 2013. URL: http://dx.doi.org/10.1137/100802888.
  27. Anupam Gupta and Amit Kumar. Online Steiner tree with deletions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA'2014), pages 455-467. Society for Industrial and Applied Mathematics, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.34.
  28. Piotr Indyk. Algorithms for dynamic geometric problems over data streams. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC'2004), pages 373-380. ACM Press, 2004. URL: http://dx.doi.org/10.1145/1007352.1007413.
  29. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. Google Scholar
  30. Gene Kan. Chapter 8: Gnutella. In Andy Oram, editor, Peer-to-Peer: Harnessing the Benefits of a Disruptive Technology. O'Reilly &Associates, 2001. Google Scholar
  31. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. SIAM Journal on Computing, 46(1):456-477, 2017. URL: http://dx.doi.org/10.1137/141002281.
  32. Michael Kapralov and David P. Woodruff. Spanners and sparsifiers in dynamic streams. In Proceedings of the 33rd ACM Symposium on Principles of Distributed Computing (PODC'2014), pages 272-281. ACM Press, 2014. Google Scholar
  33. Peter Kling, Friedhelm Meyer auf der Heide, and Peter Pietrzyk. An algorithm for online facility leasing. In Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO'2012), pages 61-72. Springer Verlag, Berlin, Heidelberg, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31104-8_6.
  34. John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis Geels, Ramakrishan Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Chris Wells, and Ben Zhao. OceanStore: An architecture for global-scale persistent storage. SIGPLAN Notices, 35(11):190-201, 2000. URL: http://dx.doi.org/10.1145/356989.357007.
  35. Christiane Lammersen and Christian Sohler. Facility location in dynamic geometric data streams. In Proceedings of the 16th Annual European Symposium on Algorithms (ESA'2008), pages 660-671. Springer Verlag, Berlin, Heidelberg, 2008. URL: http://dx.doi.org/10.1007/978-3-540-87744-8_55.
  36. Jakub Ła̧cki, Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the Steiner tree. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC'2015), pages 11-20. ACM Press, 2015. URL: http://dx.doi.org/10.1145/2746539.2746615.
  37. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. URL: http://dx.doi.org/10.1016/j.ic.2012.01.007.
  38. Andrew McGregor. Graph stream algorithms: A survey. SIGMOD Record, 43(1):9-20, 2014. URL: http://dx.doi.org/10.1145/2627692.2627694.
  39. Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816-832, 2003. URL: http://dx.doi.org/10.1137/S0097539701383443.
  40. Adam Meyerson. Online facility location. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS'2001), pages 426-431. IEEE Computer Society, 2001. URL: http://dl.acm.org/citation.cfm?id=874063.875567.
  41. Chandrashekhar Nagarajan and David P. Williamson. Offline and online facility leasing. Discrete Optimization, 10(4):361-370, 2013. URL: http://dx.doi.org/10.1016/j.disopt.2013.10.001.
  42. Daniel J. Rosenkrantz, Giri K. Tayi, and S.S. Ravi. Obtaining online approximation algorithms for facility dispersion from offline algorithms. Networks, 47(4):206-217, 2006. URL: http://dx.doi.org/10.1002/net.20109.
  43. Mário César San Felice, David P. Williamson, and Orlando Lee. A randomized O(log n)-competitive algorithm for the online connected facility location problem. Algorithmica, 76(4):1139-1157, 2016. URL: http://dx.doi.org/10.1007/s00453-016-0115-1.
  44. Rajesh Sharma and Anwitaman Datta. Supernova: Super-peers based architecture for decentralized online social networks. In Proceedings of the 4th Fourth International Conference on Communication Systems and Networks, (COMSNETS'2012), pages 1-10. IEEE, 2012. URL: http://dx.doi.org/10.1109/COMSNETS.2012.6151349.
  45. David B. Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC'1997), pages 265-274. ACM Press, 1997. URL: http://dx.doi.org/10.1145/258533.258600.
  46. Daniel Dominic Sleator and Robert Endre Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. URL: http://dx.doi.org/10.1145/2786.2793.
  47. Jouni Smed, Timo Kaukoranta, and Harri Hakonen. Networking and multiplayer computer games - the story so far. International Journal of Intelligent Games &Simulation, 2(2):101-110, 2003. Google Scholar
  48. Seeun Umboh. Online network design algorithms via hierarchical decompositions. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'2015), pages 1373-1387. Society for Industrial and Applied Mathematics, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.91.
  49. Beverly Yang and Hector Garcia-Molina. Designing a super-peer network. In Proceedings of the 19th International Conference on Data Engineering (ICDE'2003), pages 49-60. IEEE Computer Society, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact