{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T08:55:07Z","timestamp":1742979307992,"version":"3.40.3"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319266251"},{"type":"electronic","value":"9783319266268"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-26626-8_6","type":"book-chapter","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T04:08:43Z","timestamp":1449634123000},"page":"72-81","source":"Crossref","is-referenced-by-count":0,"title":["A $$(5.83+\\epsilon )$$ ( 5.83 + \u03f5 ) -Approximation Algorithm for Universal Facility Location Problem with Linear Penalties"],"prefix":"10.1007","author":[{"given":"Yicheng","family":"Xu","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,9]]},"reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-642-13036-6_12","volume-title":"Integer Programming and Combinatorial Optimization","author":"A Aggarwal","year":"2010","unstructured":"Aggarwal, A., Anand, L., Bansal, M., Garg, N., Gupta, N., Gupta, S., Jain, S.: A 3-approximation for facility location with uniform capacities. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 149\u2013162. Springer, Heidelberg (2010)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"An, H.C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. In: Proceedings of the 55th Annual Symposium on Foundations of Computer Science, pp. 256\u2013265 (2014)","DOI":"10.1109\/FOCS.2014.35"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10878-014-9711-7","volume":"29","author":"E Angel","year":"2015","unstructured":"Angel, E., Thang, N.K., Regnault, D.: Improved local search for universal facility location. J. Comb. Optim. 29, 237\u2013246 (2015)","journal-title":"J. Comb. Optim."},{"key":"6_CR4","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":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-48777-8_8","volume-title":"Integer Programming and Combinatorial Optimization","author":"FA Chudak","year":"1999","unstructured":"Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. In: Cornu\u00e9jols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610, pp. 99\u2013113. Springer, Heidelberg (1999)"},{"key":"6_CR6","unstructured":"Gupta, N., Gupta, S.: Approximation algorithms for capacitated facility location problem with penalties. \n                      arXiv:1408.4944\n                      \n                     (2014)"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"146","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, 146\u2013188 (2000)","journal-title":"J. Algorithms"},{"key":"6_CR8","doi-asserted-by":"publisher","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"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-540-39658-1_38","volume-title":"Algorithms - ESA 2003","author":"M Mahdian","year":"2003","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. lncs, vol. 2832, pp. 409\u2013421. Springer, Heidelberg (2003)"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Pal, M., Tardos, E., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 329\u2013338 (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"key":"6_CR11","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.orl.2006.08.004","volume":"35","author":"J Vygen","year":"2007","unstructured":"Vygen, J.: From stars to comets: improved local search for universal facility location. Oper. Res. Lett. 35, 427\u2013433 (2007)","journal-title":"Oper. Res. Lett."},{"key":"6_CR13","doi-asserted-by":"publisher","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":"6_CR14","doi-asserted-by":"publisher","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":"6_CR15","doi-asserted-by":"publisher","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":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-26626-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T17:18:04Z","timestamp":1559323084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-26626-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319266251","9783319266268"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-26626-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}