{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T11:00:31Z","timestamp":1776337231965,"version":"3.51.2"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,5,10]],"date-time":"2011-05-10T00:00:00Z","timestamp":1304985600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9526-1","type":"journal-article","created":{"date-parts":[[2011,5,9]],"date-time":"2011-05-09T15:43:42Z","timestamp":1304955822000},"page":"191-200","source":"Crossref","is-referenced-by-count":55,"title":["A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties"],"prefix":"10.1007","volume":"63","author":[{"given":"Donglei","family":"Du","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruixing","family":"Lu","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":[[2011,5,10]]},"reference":[{"key":"9526_CR1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"K.I. Aardal","year":"1999","unstructured":"Aardal, K.I., Chudak, F.A., Shmoys, D.B.: 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":"9526_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-level facility location problem. SIAM J. Discrete Math. 18, 207\u2013217 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9526_CR3","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":"9526_CR4","first-page":"378","volume-title":"Proceedings of the Fortieth Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location and k-median problems. In: Proceedings of the Fortieth Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 378\u2013388 (1999)"},{"key":"9526_CR5","first-page":"642","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Charikar","year":"2001","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Naraasimban, G.: Algorithms for facility location problems with outliers. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 642\u2013651 (2001)"},{"key":"9526_CR6","first-page":"79","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"F.A. Chudak","year":"2007","unstructured":"Chudak, F.A., Nagano, K.: Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovasz extension and non-smooth convex optimization. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 79\u201388 (2007)"},{"key":"9526_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"F.A. 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":"9526_CR8","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s10878-009-9213-1","volume":"20","author":"D. Du","year":"2010","unstructured":"Du, D., Wang, X., Xu, D.: An approximation algorithm for the k-level capacitated facility location problem. J. Comb. Optim. 20, 361\u2013368 (2010)","journal-title":"J. Comb. Optim."},{"key":"9526_CR9","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"L. Fleischer","year":"2003","unstructured":"Fleischer, L., Iwata, S.: A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl. Math. 131, 311\u2013322 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9526_CR10","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 strikes back: improved facility location algorithms. J. Algorithms 31, 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"key":"9526_CR11","first-page":"933","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Hayrapetyan","year":"2005","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, E.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933\u2013942 (2005)"},{"key":"9526_CR12","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-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"9526_CR13","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":"9526_CR14","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"M.R. Korupolu","year":"2000","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. J. Algorithms 37, 146\u2013188 (2000)","journal-title":"J. Algorithms"},{"key":"9526_CR15","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.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"key":"9526_CR16","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1145\/258533.258600","volume-title":"Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC)","author":"D.B. Shmoys","year":"1997","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.I.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC), pp. 265\u2013274 (1997)"},{"key":"9526_CR17","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1007\/3-540-47867-1_18","volume-title":"Proceedings of the Ninth Integer Programming and Combinatorial Optimization (IPCO)","author":"M. Sviridenko","year":"2002","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the Ninth Integer Programming and Combinatorial Optimization (IPCO), pp. 240\u2013257 (2002)"},{"key":"9526_CR18","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.orl.2005.06.002","volume":"34","author":"D. Xu","year":"2006","unstructured":"Xu, D., Du, D.: The k-level facility location game. Oper. Res. Lett. 34, 421\u2013426 (2006)","journal-title":"Oper. Res. Lett."},{"key":"9526_CR19","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. Inf. Process. Lett. 94, 119\u2013123 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9526_CR20","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/s10878-007-9127-8","volume":"17","author":"G. Xu","year":"2009","unstructured":"Xu, G., Xu, J.: An improved approximation algorithm for uncapacitated facility location problem with penalties. J. Comb. Optim. 17, 424\u2013436 (2009)","journal-title":"J. Comb. Optim."},{"key":"9526_CR21","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.orl.2007.04.002","volume":"36","author":"D. Xu","year":"2008","unstructured":"Xu, D., Zhang, S.: Approximation algorithm for facility location with service installation costs. Oper. Res. Lett. 36, 46\u201350 (2008)","journal-title":"Oper. Res. Lett."},{"key":"9526_CR22","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":"9526_CR23","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."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9526-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9526-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9526-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:07Z","timestamp":1559137507000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9526-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,10]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9526"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9526-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,10]]}}}