{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T10:01:55Z","timestamp":1743156115497,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030261757"},{"type":"electronic","value":"9783030261764"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-26176-4_49","type":"book-chapter","created":{"date-parts":[[2019,7,23]],"date-time":"2019-07-23T23:02:56Z","timestamp":1563922976000},"page":"591-602","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Universal Facility Location in Generalized Metric Space"],"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":"Yong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Zou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,21]]},"reference":[{"key":"49_CR1","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall Englewood Cliffs (1993)"},{"issue":"1","key":"49_CR2","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/151002320","volume":"46","author":"HC An","year":"2017","unstructured":"An, H.C., Singh, M., Svensson, O.: LP-based algorithms for capacitated facility location. SIAM J. Comput. 46(1), 272\u2013306 (2017)","journal-title":"SIAM J. Comput."},{"key":"49_CR3","doi-asserted-by":"crossref","unstructured":"Arora, S., Raghavan, P., Rao, S.: Approximation schemes for Euclidean $$k$$-medians and related problems. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, pp. 106\u2013113 (1998)","DOI":"10.1145\/276698.276718"},{"key":"49_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-33090-2_13","volume-title":"Algorithms \u2013 ESA 2012","author":"Manisha Bansal","year":"2012","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for capacitated facility location. In: Proceedings of the 20th Annual European Symposium on Algorithms, pp. 133\u2013144 (2012)"},{"key":"49_CR5","unstructured":"Bansal, M., Garg, N., Gupta, N.: A 5-approximation for universal facility location. In: Proceedings of the 38th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2018)"},{"key":"49_CR6","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. No. RR-388. Carnegie-Mellon University Pittsburgh Pa Management Sciences Research Group (1976)"},{"issue":"2","key":"49_CR7","doi-asserted-by":"publisher","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(2), 655\u2013685 (2015)","journal-title":"Math. Program."},{"issue":"1","key":"49_CR8","doi-asserted-by":"publisher","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(1), 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"49_CR9","doi-asserted-by":"publisher","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(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"49_CR10","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(1), 146\u2013188 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"49_CR11","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1137\/S0097539702404055","volume":"37","author":"SG Kolliopoulos","year":"2007","unstructured":"Kolliopoulos, S.G., Rao, S.: A nearly linear-time approximation scheme for the Euclidean $$k$$-median problem. SIAM J. Comput. 37(3), 757\u2013782 (2007)","journal-title":"SIAM J. Comput."},{"key":"49_CR12","doi-asserted-by":"publisher","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":"49_CR13","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-540-39658-1_38","volume-title":"Algorithms - ESA 2003","author":"Mohammad Mahdian","year":"2003","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: Proceedings of the 11th Annual European Symposium on Algorithms, pp. 409\u2013421 (2003)"},{"key":"49_CR14","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-540-45198-3_12","volume-title":"Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques","author":"Mohammad Mahdian","year":"2003","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of the Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, pp. 129\u2013140 (2003)"},{"issue":"1","key":"49_CR15","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s00493-006-0008-z","volume":"26","author":"CH Papadimitriou","year":"2006","unstructured":"Papadimitriou, C.H., Vempala, S.: On the approximability of the traveling salesman problem. Combinatorica 26(1), 101\u2013120 (2006)","journal-title":"Combinatorica"},{"key":"49_CR16","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pp. 329\u2013338 (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"key":"49_CR17","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"issue":"4","key":"49_CR18","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(4), 427\u2013433 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"1\u20132","key":"49_CR19","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10898-015-0394-0","volume":"67","author":"Y Xu","year":"2017","unstructured":"Xu, Y., Xu, D., Du, D., Wu, C.: Local search algorithm for universal facility location problem with linear penalties. J. Global Optim. 67(1\u20132), 367\u2013378 (2017)","journal-title":"J. Global Optim."},{"key":"49_CR20","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.tcs.2017.03.014","volume":"774","author":"Y Xu","year":"2019","unstructured":"Xu, Y., Xu, D., Du, D., Wu, C.: Improved approximation algorithm for universal facility location problem with linear penalties. Theoret. Comput. Sci. 774, 143\u2013151 (2019)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-26176-4_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:15:15Z","timestamp":1709824515000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-26176-4_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030261757","9783030261764"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-26176-4_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"21 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Xi'an","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ictt.xidian.edu.cn\/COCOON2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}