{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:16Z","timestamp":1740145156098,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2015,12,26]],"date-time":"2015-12-26T00:00:00Z","timestamp":1451088000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China (CN)","doi-asserted-by":"publisher","award":["Nos. 11371001 and 11531014"],"award-info":[{"award-number":["Nos. 11371001 and 11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada (CA)","doi-asserted-by":"publisher","award":["283106"],"award-info":[{"award-number":["283106"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China (CN)","doi-asserted-by":"publisher","award":["11501412"],"award-info":[{"award-number":["11501412"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s11590-015-0989-x","type":"journal-article","created":{"date-parts":[[2015,12,26]],"date-time":"2015-12-26T03:29:27Z","timestamp":1451100567000},"page":"983-993","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An approximation algorithm for the nth power metric facility location problem with linear penalties"],"prefix":"10.1007","volume":"11","author":[{"given":"Yishui","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,26]]},"reference":[{"key":"989_CR1","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum, D.S.: Heuristics for the fixed cost median problem. Math. Program. 22, 148\u2013162 (1982)","journal-title":"Math. Program."},{"key":"989_CR2","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"989_CR3","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, 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"key":"989_CR4","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":"989_CR5","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":"989_CR6","doi-asserted-by":"crossref","unstructured":"Sviridenko, M.: An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of the 9th International Integer Programming and Combinatorial Optimization Conference, pp. 240\u2013257 (2002)","DOI":"10.1007\/3-540-47867-1_18"},{"key":"989_CR7","doi-asserted-by":"crossref","first-page":"95","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, 95\u2013824 (2003)","journal-title":"J. ACM."},{"key":"989_CR8","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"key":"989_CR9","doi-asserted-by":"crossref","first-page":"74","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, 74\u2013296 (2001)","journal-title":"J. ACM."},{"key":"989_CR10","doi-asserted-by":"crossref","first-page":"11","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, 11\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"key":"989_CR11","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceeding of the 40th Annual Symposium on Foundations of Computer Science, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"989_CR12","doi-asserted-by":"crossref","first-page":"28","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, 28\u2013248 (1999)","journal-title":"J. Algorithms"},{"key":"989_CR13","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"MR 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, 46\u2013188 (2000)","journal-title":"J. Algorithms"},{"key":"989_CR14","unstructured":"Vygen, J.: Approximation algorithms facility location problems (lecture notes). Technical Report 05950-OR, Research Institute for Discrete Mathematics, University of Bonn (2005)"},{"key":"989_CR15","first-page":"149","volume":"81","author":"K Aardal","year":"1998","unstructured":"Aardal, K.: Capacitated facility location: separation algorithms and computational experience. Math. Program. 81, 149\u2013175 (1998)","journal-title":"Math. Program."},{"key":"989_CR16","doi-asserted-by":"crossref","first-page":"89","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, 89\u2013403 (2005)","journal-title":"Math. Oper. Res."},{"key":"989_CR17","doi-asserted-by":"crossref","unstructured":"Charikar, M., Li, S.: A dependent LP-rounding approach for the $$k$$ k -median problem. In: Proceeding of the 39th International Colloquium on Automata, Languages and Programming, pp. 94\u2013205 (2012)","DOI":"10.1007\/978-3-642-31594-7_17"},{"key":"989_CR18","doi-asserted-by":"crossref","first-page":"2381","DOI":"10.1007\/s11425-013-4704-z","volume":"56","author":"Y Li","year":"2013","unstructured":"Li, Y., Xiu, N.H., Xu, D.C.: An approximation algorithm for the $$k$$ k -median warehouse-retailer network design problem. Sci. China Math. 56, 2381\u20132388 (2013)","journal-title":"Sci. China Math."},{"key":"989_CR19","doi-asserted-by":"crossref","first-page":"26","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. Theor. Comput. Sci. 384, 26\u2013135 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"989_CR20","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"A Ageev","year":"2004","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 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"989_CR21","first-page":"1","volume":"57","author":"G Li","year":"2014","unstructured":"Li, G., Du, D., Xu, D., et al.: 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":"989_CR22","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2014.09.045","volume":"562","author":"C Wu","year":"2015","unstructured":"Wu, C., Du, D., Xu, D.: Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach. Theor. Comput. Sci. 562, 213\u2013226 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"989_CR23","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1007\/s10107-014-0821-x","volume":"153","author":"CG Fernandes","year":"2015","unstructured":"Fernandes, C.G., Meira, L.A.A., Miyazawa, F.K., Pedrosa, L.L.C.: A systematic approach to bound factor-revealing lps and its application to the metric and squared metric facility location problems. Math. Program. 153, 655\u2013685 (2015)","journal-title":"Math. Program."},{"key":"989_CR24","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 642\u2013651 (2001)"},{"key":"989_CR25","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.ipl.2004.12.007","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, 19\u2013123 (2005)","journal-title":"Inf. Process. Lett."},{"key":"989_CR26","first-page":"24","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, 24\u2013436 (2009)","journal-title":"J. Comb. Optim."},{"key":"989_CR27","doi-asserted-by":"crossref","first-page":"5","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, 5\u2013106 (2011)","journal-title":"Math. Program."},{"key":"989_CR28","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Y Li","year":"2015","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica. 73, 460\u2013482 (2015)","journal-title":"Algorithmica."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-015-0989-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11590-015-0989-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-015-0989-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-015-0989-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,2]],"date-time":"2019-09-02T19:47:14Z","timestamp":1567453634000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11590-015-0989-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,26]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["989"],"URL":"https:\/\/doi.org\/10.1007\/s11590-015-0989-x","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2015,12,26]]}}}