Skip to main content
SpringerLink
Log in

Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We consider the facility location problem with submodular penalties (FLPSP) and the facility location problem with linear penalties (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalties, extending the recent result of Geunes et al. (Math Program 130:85–106, 2011) with linear penalties. This framework leverages existing approximation results for the original covering problems to obtain corresponding results for their counterparts with submodular penalties. Specifically, any LP-based \(\alpha \)-approximation for the original covering problem can be leveraged to obtain an \(\left( 1-e^{-1/\alpha }\right) ^{-1}\)-approximation algorithm for the counterpart with submodular penalties. Consequently, any LP-based approximation algorithm for the classical FLP (as a covering problem) can yield, via this framework, an approximation algorithm for the counterpart with submodular penalties. Second, by exploiting some special properties of submodular/linear penalty function, we present an LP rounding algorithm which has the currently best \(2\)-approximation ratio over the previously best \(2.375\) by Li et al. (Theoret Comput Sci 476:109–117, 2013) for the FLPSP and another LP-rounding algorithm which has the currently best \(1.5148\)-approximation ratio over the previously best \(1.853\) by Xu and Xu (J Comb Optim 17:424–436, 2008) for the FLPLP, respectively.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. Aardal, K.I., Chudak, F.A., Shmoys, D.B.: A \(3\)-approximation algorithm for the \(k\)-level uncapacitated facility location problem. Info. Process. Lett. 72, 161–167 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  2. Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the \(k\)-level facility location problem. SIAM J. Discrete Math. 18, 207–217 (2003)

    Article  MathSciNet  Google Scholar 

  3. Byrka, J., Li, S., Rybicki, B.: Improved approximation algorithm for \(k\)-level UFL with penalties. In: Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA), pp. 85–96 (2013)

  4. Byrka, J., Aardal, K.I.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39, 2212–2231 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  5. Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and \(k\)-median problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 378–388 (1999)

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

  7. Chen, X., Chen, B.: Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica 53, 263–297 (2007)

    Article  Google Scholar 

  8. Chudak, F.A., Nagano, K.: Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 79–88 (2007)

  9. Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1–25 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  10. Du, D., Lu, R., Xu, D.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63, 191–200 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, 2nd edn. Elsevier, Amsterdam (2005)

    Google Scholar 

  12. Geunes, J., Levi, R., Romeijn, H.E., Shmoys, D.B.: Approximation algorithms for supply chain planning and logistics problems with market choice. Math. Program. 130, 85–106 (2011)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

  15. Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 731–740 (2002)

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  18. Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1–10 (1998)

  19. Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear/submodular penalty. In: Proceedings of the 19th Annual International Computing and Combinatorics Conference (COCOON), pp. 292–303 (2013)

  20. Li, Y., Du, D., Xiu, N., Xu, D.: A combinatorial \(2.375\)-approximation algorithm for the facility location problem with submodular penalties. Theoret. Comput. Sci. 476, 109–117 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  21. Li, S.: A \(1.488\) approximation algorithm for the uncapacitated facility location problem. Info. Comput. 222, 45–58 (2013)

    Article  MATH  Google Scholar 

  22. Mahdian, M.: Facility location and the analysis of algorithms through factor-revealing programs. Ph. D. thesis, MIT, Cambridge, MA (2004)

  23. Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411–432 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  24. Shmoys, D.B., Tardös, E., Aardal, K.I.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), pp. 265–274 (1997)

  25. Shmoys, D.B., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53, 978–1012 (2006)

    Article  MathSciNet  Google Scholar 

  26. Shu, J., Teo, C.P., Shen, Z.J.: Max: stochastic transportation-inventory network design problem. Oper. Res. 53, 48–60 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  27. Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of 9th International Integer Programming and Combinatorial Optimization Conference (IPCO), pp. 240–257 (2002)

  28. Vygen, J.: Approximation algorithms for facility location problems (Lecture Notes). Report No. 05950-OR, Research Institute for Discrete Mathematics, University of Bonn, http://www.or.uni-bonn.de/vygen/fl. Accessed (2005)

  29. Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Info. Process. Lett. 94, 119–123 (2005)

    Article  MATH  Google Scholar 

  30. Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 424–436 (2008)

    Article  Google Scholar 

  31. Ye, Y., Zhang, J.: An approximation algorithm for the dynamic facility location problem. Combinatorial Optimization in Communication Networks, pp. 623–637. Kluwer Academic Publishers, Norwell MA (2005)

  32. Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30, 389–403 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  33. Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108, 159–176 (2006)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the three anonymous referees for their valuable comments which greatly improved the manuscript. Particularly, one of the referees points out a key difference between Algorithm 4.2 and that in Li [21], which leads to a clarification on the definitions for various distances and a complete proof for Lemma 4.3. The fourth author thank Fengmin Wang, Yishui Wang, and Chenchen Wu for helpful discussions. This work was partially done while the first author was a visiting doctorate student at the Faculty of Business Administration, University of New Brunswick and supported in part by NSERC Grants 283103. The research of the second author is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 283106. The third author’s research is supported by the National Basic Research Program of China (No. 2010CB732501). The fourth author’s research is supported by NSF of China (Nos. 11071268, 11371001) and China Scholarship Council.

Author information

Authors and Affiliations

  1. Department of Mathematics, School of Science, Beijing Jiaotong University, 3 Shangyuancun, Haidian District, Beijing , 100044, People’s Republic of China

    Yu Li & Naihua Xiu

  2. Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3, Canada

    Donglei Du

  3. Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124, People’s Republic of China

    Dachuan Xu

Authors
  1. Yu Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Donglei Du
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Naihua Xiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dachuan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dachuan Xu.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, Y., Du, D., Xiu, N. et al. Improved Approximation Algorithms for the Facility Location Problems with Linear/Submodular Penalties. Algorithmica 73, 460–482 (2015). https://doi.org/10.1007/s00453-014-9911-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-014-9911-7

Keywords

Search

Navigation