Ordered k-Median with Outliers

Authors Shichuan Deng, Qianfan Zhang



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.34.pdf
  • Filesize: 0.89 MB
  • 22 pages

Document Identifiers

Author Details

Shichuan Deng
  • IIIS, Tsinghua University, Beijing, China
Qianfan Zhang
  • IIIS, Tsinghua University, Beijing, China

Cite AsGet BibTex

Shichuan Deng and Qianfan Zhang. Ordered k-Median with Outliers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 34:1-34:22, Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.34

Abstract

We study a natural generalization of the celebrated ordered k-median problem, named robust ordered k-median, also known as ordered k-median with outliers. We are given facilities β„± and clients π’ž in a metric space (β„±βˆͺπ’ž,d), parameters k,m ∈ β„€_+ and a non-increasing non-negative vector w ∈ ℝ_+^m. We seek to open k facilities F βŠ† β„± and serve m clients C βŠ† π’ž, inducing a service cost vector c = {d(j,F):j ∈ C}; the goal is to minimize the ordered objective w^⊀c^↓, where d(j,F) = min_{i ∈ F}d(j,i) is the minimum distance between client j and facilities in F, and c^↓ ∈ ℝ_+^m is the non-increasingly sorted version of c. Robust ordered k-median captures many interesting clustering problems recently studied in the literature, e.g., robust k-median, ordered k-median, etc. We obtain the first polynomial-time constant-factor approximation algorithm for robust ordered k-median, achieving an approximation guarantee of 127. The main difficulty comes from the presence of outliers, which already causes an unbounded integrality gap in the natural LP relaxation for robust k-median. This appears to invalidate previous methods in approximating the highly non-linear ordered objective. To overcome this issue, we introduce a novel yet very simple reduction framework that enables linear analysis of the non-linear objective. We also devise the first constant-factor approximations for ordered matroid median and ordered knapsack median using the same framework, and the approximation factors are 19.8 and 41.6, respectively.

Subject Classification

ACM Subject Classification
  • Theory of computation β†’ Facility location and clustering
Keywords
  • clustering
  • approximation algorithm
  • design and analysis of algorithms

Metrics

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

References

  1. Ali Aouad and Danny Segev. The ordered k-median problem: surrogate models and approximation algorithms. Math. Program., 177(1-2):55-83, 2019. URL: https://doi.org/10.1007/s10107-018-1259-3.
  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 J. Comput., 33(3):544-562, 2004. URL: https://doi.org/10.1137/S0097539702416402.
  3. Jaroslaw Byrka, Thomas W. Pensyl, Bartosz Rybicki, Joachim Spoerhase, Aravind Srinivasan, and Khoa Trinh. An improved approximation algorithm for knapsack median using sparsification. Algorithmica, 80(4):1093-1114, 2018. URL: https://doi.org/10.1007/s00453-017-0294-4.
  4. Jaroslaw Byrka, Thomas W. 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. URL: https://doi.org/10.1145/2981561.
  5. Jaroslaw 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.
  6. Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center problem. ACM Trans. Algorithms, 16(4):46:1-46:19, 2020. URL: https://doi.org/10.1145/3392720.
  7. 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 of LIPIcs, pages 29:1-29:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.29.
  8. 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.
  9. 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. URL: https://doi.org/10.1006/jcss.2002.1882.
  10. Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, pages 642-651, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365555.
  11. Moses Charikar and Shi Li. A dependent LP-rounding approach for the k-median problem. In Automata, Languages, and Programming - 39th International Colloquium, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 194-205, 2012. URL: https://doi.org/10.1007/978-3-642-31594-7_17.
  12. 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.
  13. Ke Chen. A constant factor approximation algorithm for k-median clustering with outliers. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 826-835, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347173.
  14. Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu, Hoon Oh, and David Saulpic. An improved local search algorithm for k-median. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, pages 1556-1612. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.65.
  15. Jack R. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization - Eureka, You Shrink!, volume 2570 of Lecture Notes in Computer Science, pages 11-26. Springer, 2001. URL: https://doi.org/10.1007/3-540-36478-1_2.
  16. Anupam Gupta, Benjamin Moseley, and Rudy Zhou. Structural iterative rounding for generalized k-median problems. In 48th International Colloquium on Automata, Languages, and Programming, volume 198 of LIPIcs, pages 77:1-77:18, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.77.
  17. David G. Harris, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. A lottery model for center-type problems with outliers. ACM Transactions on Algorithms, 15(3):36:1-36:25, 2019. URL: https://doi.org/10.1145/3311953.
  18. 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.
  19. Sharat Ibrahimpur and Chaitanya Swamy. Minimum-norm load balancing is (almost) as easy as minimizing makespan. In 48th International Colloquium on Automata, Languages, and Programming, volume 198 of LIPIcs, pages 81:1-81:20, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.81.
  20. Kamal Jain, Mohammad Mahdian, and Amin Saberi. A new greedy approach for facility location problems. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, pages 731-740, 2002. URL: https://doi.org/10.1145/509907.510012.
  21. 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. URL: https://doi.org/10.1145/375827.375845.
  22. Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. The matroid median problem. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1117-1130, 2011. URL: https://doi.org/10.1137/1.9781611973082.84.
  23. Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 646-659, 2018. URL: https://doi.org/10.1145/3188745.3188882.
  24. Amit Kumar. Constant factor approximation algorithm for the knapsack median problem. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 824-832, 2012. URL: https://doi.org/10.1137/1.9781611973099.66.
  25. Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh. Iterative methods in combinatorial optimization, volume 46. Cambridge University Press, 2011. Google Scholar
  26. Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. SIAM J. Comput., 45(2):530-547, 2016. URL: https://doi.org/10.1137/130938645.
  27. Chaitanya Swamy. Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Trans. Algorithms, 12(4):49:1-49:22, 2016. URL: https://doi.org/10.1145/2963170.
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