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

An Improved Approximation Algorithm for Squared Metric k-Facility Location

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

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

Abstract

In this paper, we study the squared metric k-facility location problem, which generalizes the k-means problem in that each facility has a specific cost of opening it in the solution. The current best approximation guarantee for the squared metric k-facility location problem is a ratio of \(44.473+\epsilon \) based on a local search algorithm. We give a \((36.343+\epsilon )\)-approximation for the problem using the techniques of primal-dual and Lagrangian relaxation. We propose a new rounding approach that exploits the properties of the squared metric, which is the crucial step in getting the improved approximation ratio.

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
$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 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.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

References

  1. Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.: Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms. SIAM J. Comput. 49(4), FOCS17:97–FOCS17:156 (2020)

    Google Scholar 

  2. Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245–248 (2009)

    Article  Google Scholar 

  3. Arthur, D., Vassilvitskii, S.: \(k\)-means++: the advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1027–1035 (2007)

    Google Scholar 

  4. 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 

  5. Baev, I.D., Rajaraman, R., Swamy, C.: Approximation algorithms for data placement problems. SIAM J. Comput. 38(4), 1411–1429 (2008)

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

    Google Scholar 

  7. Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 642–651 (2001)

    Google Scholar 

  8. 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 

  9. Cohen-Addad, V., Klein, P.N., Mathieu, C.: Local search yields approximation schemes for \(k\)-means and \(k\)-median in Euclidean and minor-free metrics. SIAM J. Comput. 48(2), 644–667 (2019)

    Article  MathSciNet  Google Scholar 

  10. Cura, T.: A parallel local search approach to solving the uncapacitated warehouse location problem. Comput. Ind. Eng. 59(4), 1000–1009 (2010)

    Article  Google Scholar 

  11. Feng, Q., Zhang, Z., Shi, F., Wang, J.: An improved approximation algorithm for the \(k\)-means problem with penalties. In: Proceedings of the 13th International Workshop on Frontiers in Algorithmics (FAW), pp. 170–181 (2019)

    Google Scholar 

  12. Fernandes, C.G., Meira, L.A.A., Miyazawa, F.K., Pedrosa, L.L.C.: A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Math. Program. 153(2), 655–685 (2015)

    Article  MathSciNet  Google Scholar 

  13. Friggstad, Z., Rezapour, M., Salavatipour, M.R.: Local search yields a PTAS for \(k\)-means in doubling metrics. SIAM J. Comput. 48(2), 452–480 (2019)

    Article  MathSciNet  Google Scholar 

  14. Golubchik, L., Khanna, S., Khuller, S., Thurimella, R., Zhu, A.: Approximation algorithms for data placement on parallel disks. ACM Trans. Algor. 5(4), 34:1–34:26 (2009)

    Google Scholar 

  15. Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. J. Algor. 31(1), 228–248 (1999)

    Article  MathSciNet  Google Scholar 

  16. Gupta, A., Guruganesh, G., Schmidt, M.: Approximation algorithms for aversion \(k\)-clustering via local \(k\)-median. In: Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 1–13 (2016)

    Google Scholar 

  17. Gupta, A., Tangwongsan, K.: Simpler analyses of local search algorithms for facility location. CoRR abs/0809.2554 (2008)

    Google Scholar 

  18. Hajiaghayi, M., Khandekar, R., Kortsarz, G.: Local search algorithms for the red-blue median problem. Algorithmica 63(4), 795–814 (2012)

    Article  MathSciNet  Google Scholar 

  19. Hayrapetyan, A., Swamy, C., Tardos, É.: Network design for information networks. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942 (2005)

    Google Scholar 

  20. 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 

  21. 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 

  22. Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for \(k\)-means clustering. Comput. Geom. 28, 89–112 (2004)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  24. Michel, L., Hentenryck, P.V.: A simple tabu search for warehouse location. Eur. J. Oper. Res. 157(3), 576–591 (2004)

    Article  MathSciNet  Google Scholar 

  25. Wang, S., Bi, J., Wu, J., Vasilakos, A.V.: CPHR: In-network caching for information-centric networking with partitioning and hash-routing. IEEE/ACM Trans. Netw. 24(5), 2742–2755 (2016)

    Article  Google Scholar 

  26. Wu, C., Du, D., Xu, D.: An approximation algorithm for the \(k\)-median problem with uniform penalties via pseudo-solution. Theor. Comput. Sci. 749, 80–92 (2018)

    Article  MathSciNet  Google Scholar 

  27. Zhang, D., Xu, D., Wang, Y., Zhang, P., Zhang, Z.: A local search approximation algorithm for a squared metric \(k\)-facility location problem. J. Comb. Optim. 35(4), 1168–1184 (2018)

    Article  MathSciNet  Google Scholar 

  28. Zhang, P.: A new approximation algorithm for the \(k\)-facility location problem. Theor. Comput. Sci. 384(1), 126–135 (2007)

    Article  MathSciNet  Google Scholar 

  29. Zhang, Z., Feng, Q., Huang, J., Guo, Y., Xu, J., Wang, J.: A local search algorithm for \(k\)-means with outliers. Neurocomputing 450, 230–241 (2021)

    Article  Google Scholar 

  30. Zhang, Z., Feng, Q., Xu, J., Wang, J.: An approximation algorithm for \(k\)-median with priorities. Sci. China Inf. Sci. 64(5), 150104 (2021)

    Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Zhen Zhang & Qilong Feng

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

    Zhen Zhang

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). An Improved Approximation Algorithm for Squared Metric k-Facility Location. 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_42

Download citation

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

  • 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

Search

Navigation