[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Separating \(k\text {-}\textsc {Median}\) from the Supplier Version

  • Conference paper
  • First Online:
Integer Programming and Combinatorial Optimization (IPCO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14679))

  • 585 Accesses

Abstract

Given a metric space (V, d) along with an integer k, the \(k\text {-}\textsc {Median}\) problem asks to open k centers \(C \subseteq V\) to minimize \(\sum _{v \in V} d(v, C)\), where \(d(v, C) := \min _{c \in C} d(v, c)\). While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set \(F \subseteq V\) is given with the restriction \(C \subseteq F\), the best known hardness for these two versions are \(1+1/e \approx 1.36\) and \(1+2/e \approx 1.73\) respectively, using the same reduction from \(\textsc {Maximum}~k\text {-}\textsc {Coverage} \). We prove the following two results separating them.

  1. 1.

    We give a 1.546-parameterized approximation algorithm that runs in time \(f(k) n^{O(1)}\). Since \(1+2/e\) is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original \(k\text {-}\textsc {Median}\) from the supplier version.

  2. 2.

    We prove a 1.416-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. This is achieved via a new fine-grained hardness of \(\textsc {Maximum}~k\text {-}\textsc {Coverage} \) for small set sizes.

Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.

E. Lee—Supported in part by NSF grant CCF-2236669 and Google.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Typically, it is stated in terms of the dual set system where the input is a set system, and the goal is to choose k sets whose union size is maximized.

References

  1. Adamczyk, M., Byrka, J., Marcinkowski, J., Meesum, S.M., Wlodarczyk, M.: Constant-factor FPT approximation for capacitated k-median. In: 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)

    Google Scholar 

  2. Agrawal, A., Inamdar, T., Saurabh, S., Xue, J.: Clustering what matters: optimal approximation for clustering with outliers. J. Artif. Intell. Res. 78, 143–166 (2023)

    Article  MathSciNet  Google Scholar 

  3. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for k-median and facility location problems. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 21–29 (2001)

    Google Scholar 

  4. Badanidiyuru, A., Kleinberg, R., Lee, H.: Approximating low-dimensional coverage problems. In: Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry, pp. 161–170 (2012)

    Google Scholar 

  5. Bandyapadhyay, S., Fomin, F.V., Golovach, P.A., Purohit, N., Simonov, K.: FPT approximation for fair minimum-load clustering. In: 17th International Symposium on Parameterized and Exact Computation (2022)

    Google Scholar 

  6. Bandyapadhyay, S., Lochet, W., Saurabh, S.: FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. In: 39th International Symposium on Computational Geometry (SoCG 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2023)

    Google Scholar 

  7. Bartal, Y.: On approximating arbitrary metrices by tree metrics. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 161–168 (1998)

    Google Scholar 

  8. Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms (TALG) 13(2), 1–31 (2017)

    Article  MathSciNet  Google Scholar 

  9. Charikar, M., Chekuri, C., Goel, A., Guha, S.: Rounding via trees: deterministic approximation algorithms for group Steiner trees and k-median. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp. 114–123 (1998)

    Google Scholar 

  10. Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 378–388. IEEE (1999)

    Google Scholar 

  11. Charikar, M., Guha, S., Tardos, É., Shmoys, D.B.: A constant-factor approximation algorithm for the k-median problem. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 1–10 (1999)

    Google Scholar 

  12. Charikar, M., Li, S.: A dependent LP-rounding approach for the k-median problem. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 194–205. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31594-7_17

    Chapter  Google Scholar 

  13. Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: Proceedings of the Forty-First Annual ACM symposium on Theory of Computing, pp. 283–292 (2009)

    Google Scholar 

  14. Cohen-Addad, V., Gupta, A., Kumar, A., Lee, E., Li, J.: Tight FPT approximations for k-median and k-means. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol. 132, pp. 42–1. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2019)

    Google Scholar 

  15. Cohen-Addad, V., Li, J.: On the fixed-parameter tractability of capacitated clustering. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), vol. 132, p. 41-1. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik (2019)

    Google Scholar 

  16. Cohen-Addad Viallat, V., Grandoni, F., Lee, E., Schwiegelshohn, C.: Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 940–986. SIAM (2023)

    Google Scholar 

  17. Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)

    Article  Google Scholar 

  18. Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 569–578 (2011)

    Google Scholar 

  19. Feng, Q., Zhang, Z., Huang, Z., Xu, J., Wang, J.: A unified framework of FPT approximation algorithms for clustering problems. In: 31st International Symposium on Algorithms and Computation (ISAAC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  20. Gowda, K.N., Pensyl, T., Srinivasan, A., Trinh, K.: Improved bi-point rounding algorithms and a golden barrier for k-median. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 987–1011. SIAM (2023)

    Google Scholar 

  21. Goyal, D., Jaiswal, R.: Tight FPT approximation for socially fair clustering. Inf. Process. Lett. 182, 106383 (2023)

    Article  MathSciNet  Google Scholar 

  22. Goyal, D., Jaiswal, R., Kumar, A.: FPT approximation for constrained metric k-median/means. In: 15th International Symposium on Parameterized and Exact Computation. p. 1 (2020)

    Google Scholar 

  23. Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31(1), 228–248 (1999)

    Article  MathSciNet  Google Scholar 

  24. Håstad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798–859 (2001)

    Article  MathSciNet  Google Scholar 

  25. Inamdar, T., Varadarajan, K.: Capacitated sum-of-radii clustering: an FPT approximation. In: 28th Annual European Symposium on Algorithms (ESA 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  26. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM (JACM) 50(6), 795–824 (2003)

    Article  MathSciNet  Google Scholar 

  27. Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM (JACM) 48(2), 274–296 (2001)

    Article  MathSciNet  Google Scholar 

  28. Jain, P., et al.: Parameterized approximation scheme for biclique-free max k-weight SAT and max coverage. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3713–3733. SIAM (2023)

    Google Scholar 

  29. Jaiswal, R., Kumar, A.: Clustering what matters in constrained settings. In: 34th International Symposium on Algorithms and Computation (2023)

    Google Scholar 

  30. Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 767–775 (2002)

    Google Scholar 

  31. Li, S., Svensson, O.: Approximating k-median via pseudo-approximation. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 901–910 (2013)

    Google Scholar 

  32. Lin, J.H., Vitter, J.S.: Approximation algorithms for geometric median problems. Inf. Process. Lett. 44(5), 245–249 (1992)

    Article  MathSciNet  Google Scholar 

  33. Lin, J.H., Vitter, J.S.: e-approximations with minimum packing constraint violation. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 771–782 (1992)

    Google Scholar 

  34. Manurangsi, P.: A note on max k-vertex cover: faster FPT-AS, smaller approximate kernel and improved approximation. In: 2nd Symposium on Simplicity in Algorithms (2019)

    Google Scholar 

  35. Xu, Y., Möhring, R.H., Xu, D., Zhang, Y., Zou, Y.: A constant FPT approximation algorithm for hard-capacitated k-means. Optim. Eng. 21, 709–722 (2020)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Michigan, Ann Arbor, USA

    Aditya Anand & Euiwoong Lee

Authors
  1. Aditya Anand
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Euiwoong Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Aditya Anand .

Editor information

Editors and Affiliations

  1. University of Bonn, Bonn, Germany

    Jens Vygen

  2. University of Wrocław, Wrocław, Poland

    Jarosław Byrka

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Anand, A., Lee, E. (2024). Separating \(k\text {-}\textsc {Median}\) from the Supplier Version. In: Vygen, J., Byrka, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2024. Lecture Notes in Computer Science, vol 14679. Springer, Cham. https://doi.org/10.1007/978-3-031-59835-7_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-59835-7_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-59834-0

  • Online ISBN: 978-3-031-59835-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics