Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 11640))
Included in the following conference series:
611Accesses
Abstract
In this paper, we consider the dynamick-level facility location problem, which is a generalization of the uncapacitatedk-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for the problem which finds a solution within 6 times the optimum. This approximation ratio under a dynamic setting coincides with that of the simple dual ascent 6-approximation algorithm for the (static) multilevel facility location problem (Bumb, 2001) with a weak triangle inequality property.
Supported by National Natural Science Foundation of China (Grant Nos. 61425024, 11531011, 11771013, 11871081, 11871280, 11471003), and National Thousand Young Talents Program, and Qing Lan Project.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aardal, K., Chudak, F.A., Shmoys, D.B.: A 3-approximation algorithm for the\(k\)-level uncapacitated facility location problem. Inf. Process. Lett.72(5–6), 161–167 (1999)
Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the\(k\)-level facility location problem. SIAM J. Discrete Math.18(1), 207–217 (2004)
Bumb, A., Kern, W.: A simple dual ascent algorithm for the multilevel facility location problem. In: Goemans, M., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX/RANDOM -2001. LNCS, vol. 2129, pp. 55–63. Springer, Heidelberg (2001).https://doi.org/10.1007/3-540-44666-4_10
Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 119–171. Wiley, New York (1990)
Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms31(1), 228–248 (1999)
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)
Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 229–242. Springer, Heidelberg (2002).https://doi.org/10.1007/3-540-45753-4_20
Meyerson, A., Munagala, K., Plotkin, S.: Cost-distance: two metric network design. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 624–630. IEEE (2000)
Shmoys, D.B., Aardal, K.I.: Approximation algorithms for facility location problems, vol. 1997. Utrecht University: Information and Computing Sciences (1997)
Van Roy, T.J., Erlenkotter, D.: A dual-based procedure for dynamic facility location. Manag. Sci.28(10), 1091–1105 (1982)
Wang, Z., Du, D., Xu, D.: A primal-dual approximation algorithm for the k-level stochastic facility location problem. In: Chen, B. (ed.) AAIM 2010. LNCS, pp. 253–260. Springer, Heidelberg (2010).https://doi.org/10.1007/978-3-642-14355-7_26
Xu, D., Du, D.: The k-level facility location game. Oper. Res. Lett.34(4), 421–426 (2006)
Ye, Y., Zhang, J.: An approximation algorithm for the dynamic facility location problem. In: Cheng, M.X., Li, Y., Du, D.Z. (eds.) Combinatorial Optimization in Communication Networks, vol. 18, pp. 623–637. Springer, Boston (2006).https://doi.org/10.1007/0-387-29026-5_22
Author information
Authors and Affiliations
State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, 210023, Jiangsu, People’s Republic of China
Limin Wang
College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua, 321004, Zhejiang, People’s Republic of China
Zhao Zhang
Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, People’s Republic of China
Dachuan Xu
School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing, 210023, Jiangsu, People’s Republic of China
Xiaoyan Zhang
- Limin Wang
Search author on:PubMed Google Scholar
- Zhao Zhang
Search author on:PubMed Google Scholar
- Dachuan Xu
Search author on:PubMed Google Scholar
- Xiaoyan Zhang
Search author on:PubMed Google Scholar
Corresponding author
Correspondence toXiaoyan Zhang.
Editor information
Editors and Affiliations
The University of Texas at Dallas, Richardson, TX, USA
Ding-Zhu Du
Hefei University of Technology, Hefei, China
Lian Li
Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
Xiaoming Sun
Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
Jialin Zhang
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, L., Zhang, Z., Xu, D., Zhang, X. (2019). An Approximation Algorithm for the Dynamick-level Facility Location Problem. In: Du, DZ., Li, L., Sun, X., Zhang, J. (eds) Algorithmic Aspects in Information and Management. AAIM 2019. Lecture Notes in Computer Science(), vol 11640. Springer, Cham. https://doi.org/10.1007/978-3-030-27195-4_26
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-27194-7
Online ISBN:978-3-030-27195-4
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative