Document Open Access Logo

Approximation Algorithms for Clustering with Dynamic Points

Authors Shichuan Deng, Jian Li, Yuval Rabani

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.37.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Shichuan Deng
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, China
Jian Li
  • Institute for Interdisciplinary Information Sciences, Tsinghua University, China
Yuval Rabani
  • The Rachel and Selim Benin School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel

Funding

Shichuan Deng and Jian Li: Supported in part by the National Natural Science Foundation of China Grant 61822203, 61772297, 61632016, 61761146003, the Zhongguancun Haihua Institute for Frontier Information Technology, Turing AI Institute of Nanjing, and Xi'an Institute for Interdisciplinary Information Core Technology. Yuval Rabani: Supported in part by ISF grant number 2553-17.

Acknowledgements

We want to thank the reviewers for their insightful and constructive comments.

Cite As Get BibTex

Shichuan Deng, Jian Li, and Yuval Rabani. Approximation Algorithms for Clustering with Dynamic Points. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.37

Abstract

In many classic clustering problems, we seek to sketch a massive data set of n points (a.k.a clients) in a metric space, by segmenting them into k categories or clusters, each cluster represented concisely by a single point in the metric space (a.k.a. the cluster’s center or its facility). The goal is to find such a sketch that minimizes some objective that depends on the distances between the clients and their respective facilities (the objective is a.k.a. the service cost). Two notable examples are the k-center/k-supplier problem where the objective is to minimize the maximum distance from any client to its facility, and the k-median problem where the objective is to minimize the sum over all clients of the distance from the client to its facility.
In practical applications of clustering, the data set may evolve over time, reflecting an evolution of the underlying clustering model. Thus, in such applications, a good clustering must simultaneously represent the temporal data set well, but also not change too drastically between time steps. In this paper, we initiate the study of a dynamic version of clustering problems that aims to capture these considerations. In this version there are T time steps, and in each time step t ∈ {1,2,… ,T}, the set of clients needed to be clustered may change, and we can move the k facilities between time steps. The general goal is to minimize certain combinations of the service cost and the facility movement cost, or minimize one subject to some constraints on the other. More specifically, we study two concrete problems in this framework: the Dynamic Ordered k-Median and the Dynamic k-Supplier problem. Our technical contributions are as follows:  
- We consider the Dynamic Ordered k-Median problem, where the objective is to minimize the weighted sum of ordered distances over all time steps, plus the total cost of moving the facilities between time steps. We present one constant-factor approximation algorithm for T = 2 and another approximation algorithm for fixed T ≥ 3. 
- We consider the Dynamic k-Supplier problem, where the objective is to minimize the maximum distance from any client to its facility, subject to the constraint that between time steps the maximum distance moved by any facility is no more than a given threshold. When the number of time steps T is 2, we present a simple constant factor approximation algorithm and a bi-criteria constant factor approximation algorithm for the outlier version, where some of the clients can be discarded. We also show that it is NP-hard to approximate the problem with any factor for T ≥ 3.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • clustering
  • dynamic points
  • multi-objective optimization

Metrics

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

Related Versions

References

  1. Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. Local-search based approximation algorithms for mobile facility location problems. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1607-1621, 2013. URL: https://doi.org/10.1137/1.9781611973105.115.
  2. Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic facility location via exponential clocks. ACM Transactions on Algorithms, 13(2):1-20, 2017. URL: https://doi.org/10.1145/2928272.
  3. Ali Aouad and Danny Segev. The ordered k-median problem: surrogate models and approximation algorithms. Mathematical Programming, 177(1-2):55-83, 2019. URL: https://doi.org/10.1007/s10107-018-1259-3.
  4. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544-562, 2004. URL: https://doi.org/10.1137/S0097539702416402.
  5. David L Black, Anoop Gupta, and Wolf-Dietrich Weber. Competitive management of distributed shared memory. COMPCON Spring 89, pages 184-185, 1989. URL: https://doi.org/10.1109/CMPCON.1989.301925.
  6. Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2):1-31, 2017. URL: https://doi.org/10.1145/2981561.
  7. Jarosław Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered k-median. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 620-631, 2018. URL: https://doi.org/10.1145/3188745.3188930.
  8. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. In 43rd International Colloquium on Automata, Languages, and Programming, volume 55, page 67, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.67.
  9. Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating between k-median and k-center: Approximation algorithms for ordered k-median. In 45th International Colloquium on Automata, Languages, and Programming, volume 107, page 29, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.29.
  10. Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 126-137, 2019. URL: https://doi.org/10.1145/3313276.3316322.
  11. Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 642-651, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365555.
  12. Moses Charikar and Shi Li. A dependent LP-rounding approach for the k-median problem. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming-Volume Part I, pages 194-205, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_17.
  13. Danny Z Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27-52, 2016. URL: https://doi.org/10.1007/s00453-015-0010-1.
  14. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 952-958, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070569.
  15. Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Saeed Seddighin. Stochastic k-server: How should Uber work? In 44th International Colloquium on Automata, Languages, and Programming, volume 80, page 126, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.126.
  16. Erik D Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Amin S Sayedi-Roshkhar, Shayan Oveisgharan, and Morteza Zadimoghaddam. Minimizing movement. ACM Transactions on Algorithms, 5(3):30, 2009. URL: https://doi.org/10.1145/1541885.1541891.
  17. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility location in evolving metrics. In International Colloquium on Automata, Languages, and Programming, pages 459-470, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_39.
  18. Zachary Friggstad and Mohammad R Salavatipour. Minimizing movement in mobile facility location problems. ACM Transactions on Algorithms, 7(3):28, 2011. URL: https://doi.org/10.1145/1978782.1978783.
  19. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM, 53(3):324-360, 2006. URL: https://doi.org/10.1145/1147954.1147956.
  20. Fabrizio Grandoni, R Ravi, Mohit Singh, and Rico Zenklusen. New approaches to multi-objective optimization. Mathematical Programming, 146(1-2):525-554, 2014. URL: https://doi.org/10.1007/s10107-013-0703-7.
  21. Mohammadtaghi Hajiaghayi, Wei Hu, Jian Li, Shi Li, and Barna Saha. A constant factor approximation algorithm for fault-tolerant k-median. ACM Transactions on Algorithms, 12(3):36, 2016. URL: https://doi.org/10.1145/2854153.
  22. David G Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. A lottery model for center-type problems with outliers. ACM Transactions on Algorithms, 15(3):1-25, 2019. URL: https://doi.org/10.1145/3311953.
  23. Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180-184, 1985. URL: https://doi.org/10.1287/moor.10.2.180.
  24. Dorit S Hochbaum and David B Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM, 33(3):533-550, 1986. URL: https://doi.org/10.1145/5925.5933.
  25. Kamal Jain and Vijay V Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. In 40th Annual Symposium on Foundations of Computer Science, pages 2-13, 1999. URL: https://doi.org/10.1109/SFFCS.1999.814571.
  26. 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. URL: https://doi.org/10.1145/375827.375845.
  27. Richard M Karp. Reducibility among combinatorial problems. 50 Years of Integer Programming 1958-2008, pages 219-241, 2010. URL: https://doi.org/10.1007/978-3-540-68279-0_8.
  28. Samir Khuller, Robert Pless, and Yoram J Sussmann. Fault tolerant k-center problems. Theoretical Computer Science, 242(1-2):237-245, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00222-9.
  29. Shi Li. Approximating capacitated k-median with (1+ε)k open facilities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 786-796, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch56.
  30. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. In Proceedings of the forty-fifth annual ACM symposium on Theory of Computing, pages 901-910, 2013. URL: https://doi.org/10.1145/2488608.2488723.
  31. Chaitanya Swamy and David B Shmoys. Fault-tolerant facility location. ACM Transactions on Algorithms, 4(4):1-27, 2008. URL: https://doi.org/10.1145/1383369.1383382.
  32. Jeffery Westbrook. Randomized algorithms for multiprocessor page migration. SIAM Journal on Computing, 23(5):951-965, 1994. URL: https://doi.org/10.1137/S0097539791199796.
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 About DROPS Imprint Privacy Contact