A Unified Framework of FPT Approximation Algorithms for Clustering Problems

Authors Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, Jianxin Wang



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.5.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Qilong Feng
  • School of Computer Science and Engineering, Central South University, Changsha, China
Zhen Zhang
  • School of Computer Science and Engineering, Central South University, Changsha, China
Ziyun Huang
  • Department of Computer Science and Software Engineering, Penn State Erie, The Behrend College, PA, USA
Jinhui Xu
  • Department of Computer Science and Engineering, State University of New York at Buffalo, NY, USA
Jianxin Wang
  • School of Computer Science and Engineering, Central South University, Changsha, China

Cite AsGet BibTex

Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. A Unified Framework of FPT Approximation Algorithms for Clustering Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.5

Abstract

In this paper, we present a framework for designing FPT approximation algorithms for many k-clustering problems. Our results are based on a new technique for reducing search spaces. A reduced search space is a small subset of the input data that has the guarantee of containing k clients close to the facilities opened in an optimal solution for any clustering problem we consider. We show, somewhat surprisingly, that greedily sampling O(k) clients yields the desired reduced search space, based on which we obtain FPT(k)-time algorithms with improved approximation guarantees for problems such as capacitated clustering, lower-bounded clustering, clustering with service installation costs, fault tolerant clustering, and priority clustering.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • clustering
  • approximation algorithms
  • fixed-parameter tractability

Metrics

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

References

  1. Niels H. Abel. Untersuchungen uber die reihe 1+¹_m x+^m(m-1)_1⋅ 2x²+⋯. Reine Angew. Math., 1:311-339, 1826. Google Scholar
  2. Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Proc. 27th Annual European Symposium on Algorithms, pages 1:1-1:14, 2019. Google Scholar
  3. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In Proc. 58th IEEE Annual Symposium on Foundations of Computer Science, pages 61-72, 2017. Google Scholar
  4. David Arthur and Sergei Vassilvitskii. k-means++: The advantages of careful seeding. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1027-1035, 2007. Google Scholar
  5. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544-562, 2004. Google Scholar
  6. Ivan D. Baev, Rajmohan Rajaraman, and Chaitanya Swamy. Approximation algorithms for data placement problems. SIAM J. Comput., 38(4):1411-1429, 2008. Google Scholar
  7. Suman K. Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Proc. 32nd Annual Conference on Neural Information Processing Systems, pages 4955-4966, 2019. Google Scholar
  8. Suman K. Bera, Deeparnab Chakrabarty, and Maryam Negahbani. Fair algorithms for clustering. CoRR, abs/1901.02393, 2019. URL: http://arxiv.org/abs/1901.02393.
  9. Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem. Theory Comput. Syst., 62(1):93-115, 2018. Google Scholar
  10. Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 722-736, 2015. Google Scholar
  11. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1-23:31, 2017. Google Scholar
  12. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci., 65(1):129-149, 2002. Google Scholar
  13. Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput., 39(3):923-947, 2009. Google Scholar
  14. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Proc. 46th International Colloquium on Automata, Languages, and Programming, pages 42:1-42:14, 2019. Google Scholar
  15. Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Proc. 46th International Colloquium on Automata, Languages, and Programming, pages 41:1-41:14, 2019. Google Scholar
  16. Hu Ding and Jinhui Xu. Solving the chromatic cone clustering problem via minimum spanning sphere. In Proc. 38th International Colloquium on Automata, Languages, and Programming, pages 773-784, 2011. Google Scholar
  17. Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1471-1490, 2015. Google Scholar
  18. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. Google Scholar
  19. Qilong Feng, Jiaxin Hu, Neng Huang, and Jianxin Wang. Improved PTAS for the constrained k-means problem. J. Comb. Optim., 37(4):1091-1110, 2019. Google Scholar
  20. Qilong Feng, Zhen Zhang, Ziyun Huang, Jinhui Xu, and Jianxin Wang. Improved algorithms for clustering with outliers. In Proc. 30th International Symposium on Algorithms and Computation, pages 61:1-61:12, 2019. Google Scholar
  21. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. J. Algorithms, 31(1):228-248, 1999. Google Scholar
  22. Yutian Guo, Junyu Huang, and Zhen Zhang. A constant factor approximation for lower-bounded k-median. In Proc. 16th Annual Conference on Theory and Applications of Models of Computation, 2020. Google Scholar
  23. Anupam Gupta and Kanat Tangwongsan. Simpler analyses of local search algorithms for facility location. CoRR, abs/0809.2554, 2008. URL: http://arxiv.org/abs/0809.2554.
  24. Mohammad T. Hajiaghayi, Wei Hu, Jian Li, Shi Li, and Barna Saha. A constant factor approximation algorithm for fault-tolerant k-median. ACM Trans. Algorithms, 12(3):36:1-36:19, 2016. Google Scholar
  25. Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V. Vazirani. Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM, 50(6):795-824, 2003. Google Scholar
  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. J. ACM, 48(2):274-296, 2001. Google Scholar
  27. Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple D²-sampling based PTAS for k-means and other clustering problems. Algorithmica, 70(1):22-46, 2014. Google Scholar
  28. Ragesh Jaiswal, Mehul Kumar, and Pulkit Yadav. Improved analysis of D²-sampling based PTAS for k-means and other clustering problems. Inf. Process. Lett., 115(2):100-103, 2015. Google Scholar
  29. Amit Kumar and Yogish Sabharwal. The priority k-median problem. In Proc. 27th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 71-83, 2007. Google Scholar
  30. Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57(2):5:1-5:32, 2010. Google Scholar
  31. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM J. Comput., 45(2):530-547, 2016. Google Scholar
  32. Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge University Press, 1995. Google Scholar
  33. David Saulpic, Vincent Cohen-Addad, and Andreas E. Feldmann. Near-linear time approximations schemes for clustering in doubling metrics. In Proc. 60th IEEE Annual Symposium on Foundations of Computer Science, pages 540-559, 2019. Google Scholar
  34. David B. Shmoys, Chaitanya Swamy, and Retsef Levi. Facility location with service installation costs. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1088-1097, 2004. Google Scholar
  35. Mauro Sozio, Thomas Neumann, and Gerhard Weikum. Near-optimal dynamic replication in unstructured peer-to-peer networks. In Proc. 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 281-290, 2008. Google Scholar
  36. Zoya Svitkina. Lower-bounded facility location. ACM Trans. Algorithms, 6(4):69:1-69:16, 2010. 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