[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Approximating the \(\tau \)-relaxed soft capacitated facility location problem

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

In this paper, we consider the \(\tau \)-relaxed soft capacitated facility location problem (\(\tau \)-relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the \(\tau \)-relaxed SCFLP, we are given a facility set \(\mathcal {F}\), a client set and a parameter \(\tau \ge 1\). Every facility \(i \in \mathcal {F}\) has a capacity \(u_i\) and an opening cost \(f_i\), and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most \(l u_i\) clients and incurs an opening cost of \(l f_i\). Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the \(\tau \)-relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based \((3 \tau + 1)\)-approximation algorithm for the \(\tau \)-relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from \(11.18+ \varepsilon \) to 10.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Aardal KI, Chudak FA, Shmoys DB (1999) A \(3\)-approximation algorithm for the \(k\)-level uncapacitated facility location problem. Inf Process Lett 72:161–167

    Article  MathSciNet  Google Scholar 

  • Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2019) Better guarantees for \(k\)-means and Euclidean \(k\)-median by primal-dual algorithms. SIAM J Comput. https://doi.org/10.1137/18M1171321

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Byrka J, Li S, Rybicki B (2016) Improved approximation algorithm for \(k\)-level uncapacitated facility location problem (with penalties). Theory Comput Syst 58:19–44

    Article  MathSciNet  Google Scholar 

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

  • Charikar M, Guha S, Tardos É, Shmoys DB (2002) A constant-factor approximation algorithm for the \(k\)-median problem. J Comput Syst Sci 65:129–149

    Article  MathSciNet  Google Scholar 

  • Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp 642–651

  • Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33:1–25

    Article  MathSciNet  Google Scholar 

  • Fernandes CG, Meira LAA, Miyazawa FK, Pedrosa LLC (2015) A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Math Program 153:655–685

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Hochbaum DS (1982) Heuristics for the fixed cost median problem. Math program 22:148–162

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Kuehn AA, Hamburger MJ (1963) A heuristic program for locating warehouses. Manag Sci 9:643–666

    Article  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Li Y, Du D, Xiu N, Xu D (2015) Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica 73:460–482

    Article  MathSciNet  Google Scholar 

  • Lin JH, Vitter JS (1992) Approximation algorithms for geometric median problems. Inf Process Lett 44:245–249

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  • Manne AS (1964) Plant location under economies-of-scale-decentralization and computation. Manag Sci 11:213–235

    Article  Google Scholar 

  • Pal M, Tardos É, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings of FOCS, pp 329–338

  • Shmoys DB, Tardos É, Aardal KI (1997) Approximation algorithms for facility location problems. In: Proceedings of STOC, pp 265–274

  • Shu J, Teo CP, Shen ZJM (2005) Stochastic transportation-inventory network design problem. Oper Res 53:48–60

    Article  MathSciNet  Google Scholar 

  • Stollsteimer JF (1963) A working model for plant numbers and locations. J Farm Econ 45:631–645

    Article  Google Scholar 

  • Sviridenko M (2002) An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of IPCO, pp 240–257

  • Teo CP, Shu J (2004) Warehouse-retailer network design problem. Oper Res 52:396–408

    Article  MathSciNet  Google Scholar 

  • Wu C, Xu D, Shu J (2013) An approximation algorithm for the stochastic fault-tolerant facility location problem. J Oper Res Soc China 1:511–522

    Article  Google Scholar 

  • Xu Y, Xu D, Zhang Y, Zou J (2020) M\(^p\)UFLP: universal facility location problem in the \(p\)-th power of metric space. Theor Comput Sci. https://doi.org/10.1016/j.tcs.2020.05.038

    Article  MATH  Google Scholar 

  • Young NE (2000) \(k\)-medians, facility location, and the Chernoff-Wald bound. In: Proceedings of SODA, pp 86–95

Download references

Acknowledgements

The first two authors are supported by Natural Science Foundation of China (No. 11531014). The second and fourth authors are supported by Natural Science Foundation of China (No. 11871081). The third author is supported by Natural Science Foundation of China (No. 11901558) and China Postdoctoral Science Foundation funded project (No. 2018M643233).

Author information

Authors and Affiliations

  1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, 100190, People’s Republic of China

    Lu Han

  2. Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing, 100124, People’s Republic of China

    Dachuan Xu

  3. Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen, 518055, People’s Republic of China

    Yicheng Xu

  4. School of Computer Science and Technology, Shandong Jianzhu University, Jinan, 250101, People’s Republic of China

    Dongmei Zhang

Authors
  1. Lu Han
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dachuan Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yicheng Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dongmei Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dongmei Zhang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A preliminary version of this paper appeared in Proceedings of the 8th International Conference on Computational Data and Social Networks, pp 72–73, 2019.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Han, L., Xu, D., Xu, Y. et al. Approximating the \(\tau \)-relaxed soft capacitated facility location problem. J Comb Optim 40, 848–860 (2020). https://doi.org/10.1007/s10878-020-00631-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-020-00631-y

Keywords

Search

Navigation