{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T05:14:35Z","timestamp":1779081275030,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,7,11]],"date-time":"2014-07-11T00:00:00Z","timestamp":1405036800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s00453-014-9911-7","type":"journal-article","created":{"date-parts":[[2014,7,10]],"date-time":"2014-07-10T11:29:07Z","timestamp":1404991747000},"page":"460-482","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":60,"title":["Improved Approximation Algorithms for the Facility Location Problems with Linear\/Submodular Penalties"],"prefix":"10.1007","volume":"73","author":[{"given":"Yu","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naihua","family":"Xiu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,7,11]]},"reference":[{"key":"9911_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"KI Aardal","year":"1999","unstructured":"Aardal, K.I., Chudak, F.A., Shmoys, D.B.: A $$3$$ 3 -approximation algorithm for the $$k$$ k -level uncapacitated facility location problem. Info. Process. Lett. 72, 161\u2013167 (1999)","journal-title":"Info. Process. Lett."},{"key":"9911_CR2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"A Ageev","year":"2003","unstructured":"Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the $$k$$ k -level facility location problem. SIAM J. Discrete Math. 18, 207\u2013217 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9911_CR3","doi-asserted-by":"crossref","unstructured":"Byrka, J., Li, S., Rybicki, B.: Improved approximation algorithm for $$k$$ k -level UFL with penalties. In: Proceedings of the 11th Workshop on Approximation and Online Algorithms (WAOA), pp. 85\u201396 (2013)","DOI":"10.1007\/978-3-319-08001-7_8"},{"key":"9911_CR4","doi-asserted-by":"crossref","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka, J., Aardal, K.I.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39, 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"key":"9911_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and $$k$$ k -median problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"9911_CR6","unstructured":"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\u2013651 (2001)"},{"key":"9911_CR7","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00453-007-9032-7","volume":"53","author":"X Chen","year":"2007","unstructured":"Chen, X., Chen, B.: Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica 53, 263\u2013297 (2007)","journal-title":"Algorithmica"},{"key":"9911_CR8","unstructured":"Chudak, F.A., Nagano, K.: Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lov\u00e1sz extension and non-smooth convex optimization. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 79\u201388 (2007)"},{"key":"9911_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1\u201325 (2003)","journal-title":"SIAM J. Comput."},{"key":"9911_CR10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D Du","year":"2012","unstructured":"Du, D., Lu, R., Xu, D.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63, 191\u2013200 (2012)","journal-title":"Algorithmica"},{"key":"9911_CR11","volume-title":"Submodular Functions and Optimization. Annals of Discrete Mathematics","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Annals of Discrete Mathematics, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"9911_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/s10107-009-0310-9","volume":"130","author":"J Geunes","year":"2011","unstructured":"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\u2013106 (2011)","journal-title":"Math. Program."},{"key":"9911_CR13","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strike back: improved facility location algorithms. J. Algorithms 31, 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"key":"9911_CR14","unstructured":"Hayrapetyan, A., Swamy, C., Tard\u00f6s, E.: Network design for information networks. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933\u2013942 (2005)"},{"key":"9911_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"9911_CR16","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and $$k$$ k -median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"9911_CR17","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"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\u2013824 (2003)","journal-title":"J. ACM"},{"key":"9911_CR18","unstructured":"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\u201310 (1998)"},{"key":"9911_CR19","doi-asserted-by":"crossref","unstructured":"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\u2013303 (2013)","DOI":"10.1007\/978-3-642-38768-5_27"},{"key":"9911_CR20","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.tcs.2012.11.037","volume":"476","author":"Y Li","year":"2013","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: A combinatorial $$2.375$$ 2.375 -approximation algorithm for the facility location problem with submodular penalties. Theoret. Comput. Sci. 476, 109\u2013117 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"9911_CR21","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","volume":"222","author":"S Li","year":"2013","unstructured":"Li, S.: A $$1.488$$ 1.488 approximation algorithm for the uncapacitated facility location problem. Info. Comput. 222, 45\u201358 (2013)","journal-title":"Info. Comput."},{"key":"9911_CR22","unstructured":"Mahdian, M.: Facility location and the analysis of algorithms through factor-revealing programs. Ph. D. thesis, MIT, Cambridge, MA (2004)"},{"key":"9911_CR23","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"key":"9911_CR24","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tard\u00f6s, 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\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"9911_CR25","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1145\/1217856.1217860","volume":"53","author":"DB Shmoys","year":"2006","unstructured":"Shmoys, D.B., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53, 978\u20131012 (2006)","journal-title":"J. ACM"},{"key":"9911_CR26","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1287\/opre.1040.0140","volume":"53","author":"J Shu","year":"2005","unstructured":"Shu, J., Teo, C.P., Shen, Z.J.: Max: stochastic transportation-inventory network design problem. Oper. Res. 53, 48\u201360 (2005)","journal-title":"Oper. Res."},{"key":"9911_CR27","doi-asserted-by":"crossref","unstructured":"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\u2013257 (2002)","DOI":"10.1007\/3-540-47867-1_18"},{"key":"9911_CR28","unstructured":"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)"},{"key":"9911_CR29","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.ipl.2005.01.005","volume":"94","author":"G Xu","year":"2005","unstructured":"Xu, G., Xu, J.: An LP rounding algorithm for approximating uncapacitated facility location problem with penalties. Info. Process. Lett. 94, 119\u2013123 (2005)","journal-title":"Info. Process. Lett."},{"key":"9911_CR30","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/s10878-007-9127-8","volume":"17","author":"G Xu","year":"2008","unstructured":"Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 424\u2013436 (2008)","journal-title":"J. Comb. Optim."},{"key":"9911_CR31","doi-asserted-by":"crossref","unstructured":"Ye, Y., Zhang, J.: An approximation algorithm for the dynamic facility location problem. Combinatorial Optimization in Communication Networks, pp. 623\u2013637. Kluwer Academic Publishers, Norwell MA (2005)","DOI":"10.1007\/0-387-29026-5_22"},{"key":"9911_CR32","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J Zhang","year":"2005","unstructured":"Zhang, J., Chen, B., Ye, Y.: A multiexchange local search algorithm for the capacitated facility location problem. Math. Oper. Res. 30, 389\u2013403 (2005)","journal-title":"Math. Oper. Res."},{"key":"9911_CR33","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10107-006-0704-x","volume":"108","author":"J Zhang","year":"2006","unstructured":"Zhang, J.: Approximating the two-level facility location problem via a quasi-greedy approach. Math. Program. 108, 159\u2013176 (2006)","journal-title":"Math. Program."},{"key":"9911_CR34","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.tcs.2007.05.024","volume":"384","author":"P Zhang","year":"2007","unstructured":"Zhang, P.: A new approximation algorithm for the $$k$$ k -facility location problem. Theoret. Comput. Sci. 384, 126\u2013135 (2007)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9911-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9911-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9911-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,12]],"date-time":"2019-08-12T13:35:21Z","timestamp":1565616921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9911-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,11]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["9911"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9911-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,11]]}}}