{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:43:44Z","timestamp":1743083024159,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319196466"},{"type":"electronic","value":"9783319196473"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19647-3_15","type":"book-chapter","created":{"date-parts":[[2015,6,26]],"date-time":"2015-06-26T09:03:08Z","timestamp":1435309388000},"page":"162-169","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Approximation Algorithms for the Multilevel Facility Location Problem with Linear\/Submodular Penalties"],"prefix":"10.1007","author":[{"given":"Gaidi","family":"Li","sequence":"first","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,27]]},"reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"K Aardal","year":"1999","unstructured":"Aardal, K., Chudak, F., Shmoys, D.: A $$3$$-approximation algorithm for the $$k$$-level uncapacitated facility location problem. Inf. Process. Lett. 72, 161\u2013167 (1999)","journal-title":"Inf. Process. Lett."},{"key":"15_CR2","series-title":"Communications in Computer and Information Science","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-540-89985-3_6","volume-title":"Proceeding of CSICC","author":"M Asadi","year":"2008","unstructured":"Asadi, M., Niknafs, A., Ghodsi, M.: An approximation algorithm for the $$k$$-level uncapacitated facility location problem with penalties. In: Sarbazi-Azad, H., Parhami, B., Miremadi, S.-G., Hessabi, S. (eds.) Proceeding of CSICC. Communications in Computer and Information Science, vol. 6, pp. 41\u201349. Springer, Heidelberg (2008)"},{"key":"15_CR3","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"A Ageev","year":"2007","unstructured":"Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the $$k$$-FLP. SIAM J. Discrete Math. 18, 207\u2013217 (2007)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-3-319-08001-7_8","volume-title":"Approximation and Online Algorithms","author":"J Byrka","year":"2014","unstructured":"Byrka, J., Li, S., Rybicki, B.: Improved approximation algorithm for k-Level UFL with penalties, a simplistic view on randomizing the scaling parameter. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 85\u201396. Springer, Heidelberg (2014)"},{"key":"15_CR5","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.dam.2009.11.007","volume":"158","author":"F Gabor","year":"2010","unstructured":"Gabor, F., Van Ommeren, J.: A new approximation algorithm for the multilevel facility location problem. Discrete Appl. Math. 158, 453\u2013460 (2010)","journal-title":"Discrete Appl. Math."},{"key":"15_CR7","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. In: Proceeding of SODA, pp. 649\u2013657 (1998)"},{"key":"15_CR8","doi-asserted-by":"publisher","first-page":"521","DOI":"10.3934\/jimo.2012.8.521","volume":"18","author":"G Li","year":"2012","unstructured":"Li, G., Wang, Z., Xu, D.: An approximation algorithm for the $$k$$-FLP with submodular penalties. J. Ind. Manage. Optim. 18, 521\u2013529 (2012)","journal-title":"J. Ind. Manage. Optim."},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.: Approximation algorithms for metric facility location and $$k$$-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274\u2013276 (2001)","journal-title":"J. ACM"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Sviridenko, M.: Inapproximability of the multi-level uncapacitated facility location problem. In: Proceeding of SODA, pp. 718\u2013734 (2012)","DOI":"10.1137\/1.9781611973099.59"},{"key":"15_CR11","first-page":"1","volume":"57","author":"G Li","year":"2014","unstructured":"Li, G., Du, D., Xu, D., Zhang, R.: A cost-sharing method for the multi-level economic lot-sizing game. Sci. China Inf. Sci. 57, 1\u20139 (2014)","journal-title":"Sci. China Inf. Sci."},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-22012-8_5","volume-title":"Automata, Languages and Programming","author":"S Li","year":"2011","unstructured":"Li, S.: A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part II. LNCS, vol. 6756, pp. 77\u201388. Springer, Heidelberg (2011)"},{"key":"15_CR13","doi-asserted-by":"publisher","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility locaiton problem with linear\/submodular penalties, Algorithmica. doi:10.1007\/s00453-014-9911-7","DOI":"10.1007\/s00453-014-9911-7"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problem (extended abstract). In: Proceeding of STOC, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"15_CR15","unstructured":"Wu, C., Xu, D.: An improved approximation algorithm for the $$k$$-FLP with soft capacities, accepted by Acta Mathematicae Applicatae Sinica"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19647-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:03:21Z","timestamp":1676945001000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19647-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319196466","9783319196473"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19647-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"27 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}