{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T15:44:25Z","timestamp":1772293465212,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T00:00:00Z","timestamp":1415059200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00224-014-9575-3","type":"journal-article","created":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T02:23:00Z","timestamp":1414981380000},"page":"19-44","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)"],"prefix":"10.1007","volume":"58","author":[{"given":"Jaroslaw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shanfei","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bartosz","family":"Rybicki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,4]]},"reference":[{"issue":"5-6","key":"9575_CR1","doi-asserted-by":"crossref","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(5-6), 161\u2013167 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9575_CR2","doi-asserted-by":"crossref","unstructured":"Ageev, A., Ye, Y., Zhang, J.: Improved combinatorial approximation algorithms for the k-level facility location problem. ICALP, 145\u2013156 (2003)","DOI":"10.1007\/3-540-45061-0_13"},{"key":"9575_CR3","first-page":"41","volume":"6","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 CSICC. CCIS 6, 41\u201349 (2008)","journal-title":"CCIS"},{"key":"9575_CR4","volume-title":"Approximation algorithms for facility location problems","author":"A Bumb","year":"2002","unstructured":"Bumb, A.: Approximation algorithms for facility location problems. University of Twente, PHD thesis (2002)"},{"issue":"6","key":"9575_CR5","doi-asserted-by":"crossref","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39(6), 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"key":"9575_CR6","doi-asserted-by":"crossref","unstructured":"Byrka, J., Li, S., Rybicki, B.: Improved approximation algorithm for k-level UFL with penalties, a simplistic view on randomizing the scaling parameter (2013)","DOI":"10.1007\/978-3-319-08001-7_8"},{"key":"9575_CR7","doi-asserted-by":"crossref","unstructured":"Byrka, J., Rybicki, B.: Improved LP-Rounding Approximation Algorithm for k-level Uncapacitated Facility Location ICALP (1), pp 157\u2013169 (2012)","DOI":"10.1007\/978-3-642-31594-7_14"},{"key":"9575_CR8","unstructured":"Byrka, J., Ghodsi, M., Srinivasan, A.: LP-rounding algorithms for facility-location problems CoRR abs\/1007, p 3611 (2010)"},{"key":"9575_CR9","unstructured":"Charikar, M., Khuller, S., Mount, D., Narasimhan, G.: Algorithms for facility location problems with outliers. SODA, 642\u2013651 (2001)"},{"issue":"1","key":"9575_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"F Chudak","year":"2003","unstructured":"Chudak, F., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33(1), 1\u201325 (2003)","journal-title":"SIAM J. Comput."},{"key":"9575_CR11","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem, SODA, pp 253\u2013259 (1998)"},{"issue":"1","key":"9575_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., Shmoys, D.: Approximation algorithms for supply chain planning and logistics problems with market choice. Math. Program. 130(1), 85\u2013106 (2011)","journal-title":"Math. Program."},{"issue":"1","key":"9575_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 strikes back: improved facility location algorithms. J. Algorithm. 31(1), 228\u2013248 (1999)","journal-title":"J. Algorithm."},{"issue":"6","key":"9575_CR14","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.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"key":"9575_CR15","doi-asserted-by":"crossref","unstructured":"Krishnaswamy, R., Sviridenko, M.: Inapproximability of the multi-level uncapacitated facility location problem, SODA, pp 718\u2013734 (2012)","DOI":"10.1137\/1.9781611973099.59"},{"key":"9575_CR16","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 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45\u201358 (2013)","journal-title":"Inf. Comput."},{"key":"9575_CR17","doi-asserted-by":"crossref","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithm for the facility location problems with linear\/submodular penalties. COCOON, 292\u2013303 (2013)","DOI":"10.1007\/978-3-642-38768-5_27"},{"key":"9575_CR18","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (extended abstract), STOC, pp 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"9575_CR19","doi-asserted-by":"crossref","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location Problem, IPCO, pp 240\u2013257 (2002)","DOI":"10.1007\/3-540-47867-1_18"},{"issue":"3","key":"9575_CR20","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(3), 119\u2013123 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9575_CR21","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(4), 424\u2013436 (2009)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"9575_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(1), 159\u2013176 (2006)","journal-title":"Math. Program."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9575-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9575-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9575-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,16]],"date-time":"2019-08-16T19:15:08Z","timestamp":1565982908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9575-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,4]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9575"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9575-3","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,4]]}}}