Document Open Access Logo

Approximation Algorithms for Aversion k-Clustering via Local k-Median

Authors Anupam Gupta, Guru Guruganesh, Melanie Schmidt

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.66.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Anupam Gupta
Guru Guruganesh
Melanie Schmidt

Cite As Get BibTex

Anupam Gupta, Guru Guruganesh, and Melanie Schmidt. Approximation Algorithms for Aversion k-Clustering via Local k-Median. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 66:1-66:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.66

Abstract

In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clustering is the sum of all these per-point-costs. This problem is motivated by questions in generating automatic abstractions of extensive-form games.

We reduce this problem to a "local" k-median problem where each facility has a prescribed radius and can only connect to clients within that radius. Our main results is a constant-factor approximation algorithm for the aversion k-clustering problem via the local k-median problem.

We use a primal-dual approach; our technical contribution is a non-local rounding step which we feel is of broader interest.

Subject Classification

Keywords
  • Approximation algorithms
  • clustering
  • k-median
  • primal-dual

Metrics

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

References

  1. Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Mathematical Programming, 154(1-2):29-53, 2015. Google Scholar
  2. 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. Google Scholar
  3. Michel Louis Balinski. On finding integer solutions to linear programs. Technical report, DTIC Document, 1964. Google Scholar
  4. Yair Bartal, Moses Charikar, and Danny Raz. Approximating min-sum k-clustering in metric spaces. In Proceedings of the 33rd STOC, pages 11-20, 2001. Google Scholar
  5. Babak Behsaz, Zachary Friggstad, Mohammad R. Salavatipour, and Rohit Sivakumar. Approximation algorithms for min-sum k-clustering and balanced k-median. In Proceedings of the 42nd ICALP, pages 116-128, 2015. Google Scholar
  6. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the 26th SODA, pages 737-756, 2015. Google Scholar
  7. Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for facility location problems. SIAM Journal on Computing, 34(4):803-824, 2005. Google Scholar
  8. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-149, 2002. Google Scholar
  9. Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. Journal of Computer and System Sciences, 68(2):417-441, 2004. Google Scholar
  10. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the 16th SODA, pages 952-958, 2005. Google Scholar
  11. Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In Proceedings of the 53rd FOCS, pages 273-282, 2012. Google Scholar
  12. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  13. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-248, 1999. Google Scholar
  14. Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10:180-184, 1985. Google Scholar
  15. Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discrete Applied Mathematics, 1:209-215, 1979. Google Scholar
  16. Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings of the 34th STOC, pages 731-740, 2002. Google Scholar
  17. 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
  18. Richard M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  19. Christian Kroer and Tuomas Sandholm. Extensive-Form Game Imperfect-Recall Abstractions With Bounds. CoRR, abs/1409.3302, 2014. also published at the Algorithmic Game Theory workshop at IJCAI, 2015. Google Scholar
  20. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Information and Computation, 222:45-58, 2013. Google Scholar
  21. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. In Proceedings of the 45th STOC, pages 901-910, 2013. Google Scholar
  22. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Available at URL: http://www.designofapproxalgs.com.
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