Improved Parameterized Approximation for Balanced k-Median | SpringerLink
Skip to main content
Springer Nature Link
Log in

Improved Parameterized Approximation for Balanced k-Median

  • Conference paper
  • First Online:
Combinatorial Optimization and Applications (COCOA 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13135))

  • 1022 Accesses

Abstract

Balanced k-median is a frequently encountered problem in applications requiring balanced clustering results, which generalizes the standard k-median problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. This problem is known to be W[2]-hard if parameterized by k, implying that the existence of an FPT(k)-time exact algorithm is unlikely. In this paper, we give a \((3+\epsilon )\)-approximation algorithm for balanced k-median that runs in FPT(k) time, improving upon the previous best approximation ratio of \(7.2+\epsilon \) obtained in the same time. The crucial step in getting the improved ratio and our main technical contribution is a different random sampling method for selecting opened facilities.

This work was supported by National Natural Science Foundation of China (61872450 and 62172446).

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
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • 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

References

  1. Adamczyk, M., Byrka, J., Marcinkowski, J., Meesum, S.M., Wlodarczyk, M.: Constant-factor FPT approximation for capacitated \(k\)-median. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA), pp. 1:1–1:14 (2019)

    Google Scholar 

  2. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for \(k\)-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004)

    Article  MathSciNet  Google Scholar 

  3. Aydin, K., Bateni, M., Mirrokni, V.S.: Distributed balanced partitioning via linear embedding. In: Proceedings of the 9th ACM International Conference on Web Search and Data Mining (WSDM), pp. 387–396 (2016)

    Google Scholar 

  4. Bateni, M., Bhaskara, A., Lattanzi, S., Mirrokni, V.S.: Distributed balanced clustering via mapping coresets. In: Proceedings of the 27th Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 2591–2599 (2014)

    Google Scholar 

  5. Borgwardt, S., Brieden, A., Gritzmann, P.: An LP-based \(k\)-means algorithm for balancing weighted point sets. Eur. J. Oper. Res. 263(2), 349–355 (2017)

    Article  MathSciNet  Google Scholar 

  6. 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 13(2), 23:1–23:31 (2017)

    Google Scholar 

  7. Charikar, M., Li, S.: A dependent LP-rounding approach for the \(k\)-median problem. In: Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 194–205 (2012)

    Google Scholar 

  8. Cohen-Addad, V., Gupta, A., Kumar, A., Lee, E., Li, J.: Tight FPT approximations for \(k\)-median and \(k\)-means. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 42:1–42:14 (2019)

    Google Scholar 

  9. Cohen-Addad, V., Li, J.: On the fixed-parameter tractability of capacitated clustering. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 41:1–41:14 (2019)

    Google Scholar 

  10. Demirci, H.G., Li, S.: Constant approximation for capacitated \(k\)-median with \((1+\epsilon )\)-capacity violation. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 73:1–73:14 (2016)

    Google Scholar 

  11. Dick, T., Li, M., Pillutla, V.K., White, C., Balcan, N., Smola, A.J.: Data driven resource allocation for distributed learning. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 662–671 (2017)

    Google Scholar 

  12. Ding, H.: Faster balanced clusterings in high dimension. Theor. Comput. Sci. 842, 28–40 (2020)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. Guo, Y., Huang, J., Zhang, Z.: A constant factor approximation for lower-bounded \(k\)-median. In: Proceedings of the 16th International Conference on Theory and Applications of Models of Computation (TAMC), pp. 119–131 (2020)

    Google Scholar 

  15. Han, L., Hao, C., Wu, C., Zhang, Z.: Approximation algorithms for the lower-bounded \(k\)-median and its generalizations. In: Proceedings of the 26th International Conference on Computing and Combinatorics (COCOON), pp. 627–639 (2020)

    Google Scholar 

  16. 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 50(6), 795–824 (2003)

    Article  MathSciNet  Google Scholar 

  17. 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 48(2), 274–296 (2001)

    Article  MathSciNet  Google Scholar 

  18. Li, S.: Approximating capacitated \(k\)-median with \((1+\epsilon )k\) open facilities. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 786–796 (2016)

    Google Scholar 

  19. Li, S.: On uniform capacitated \(k\)-median beyond the natural LP relaxation. ACM Trans. Algorithms 13(2), 22:1–22:18 (2017)

    Google Scholar 

  20. Li, S., Svensson, O.: Approximating \(k\)-median via pseudo-approximation. SIAM J. Comput. 45(2), 530–547 (2016)

    Article  MathSciNet  Google Scholar 

  21. Lin, W., He, Z., Xiao, M.: Balanced clustering: a uniform model and fast algorithm. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2987–2993 (2019)

    Google Scholar 

  22. Manurangsi, P., Raghavendra, P.: A birthday repetition theorem and complexity of approximating dense CSPs. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 78:1–78:15 (2017)

    Google Scholar 

  23. Siavoshi, S., Kavian, Y.S., Sharif, H.: Load-balanced energy efficient clustering protocol for wireless sensor networks. IET Wirel. Sens. Syst. 6(3), 67–73 (2016)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Frontier Crossover Studies, Hunan University of Technology and Business, Changsha, 410000, People’s Republic of China

    Zhen Zhang

  2. School of Computer Science and Engineering, Central South University, Changsha, 410000, People’s Republic of China

    Zhen Zhang & Qilong Feng

Authors
  1. Zhen Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Qilong Feng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qilong Feng .

Editor information

Editors and Affiliations

  1. University of Texas at Dallas, Richardson, TX, USA

    Ding-Zhu Du

  2. University of New Brunswick, Fredericton, NB, Canada

    Donglei Du

  3. Tianjin University of Technology, Tianjin, China

    Chenchen Wu

  4. Beijing University of Technology, Beijing, China

    Dachuan Xu

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Zhang, Z., Feng, Q. (2021). Improved Parameterized Approximation for Balanced k-Median. In: Du, DZ., Du, D., Wu, C., Xu, D. (eds) Combinatorial Optimization and Applications. COCOA 2021. Lecture Notes in Computer Science(), vol 13135. Springer, Cham. https://doi.org/10.1007/978-3-030-92681-6_49

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-92681-6_49

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-92680-9

  • Online ISBN: 978-3-030-92681-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics