{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T22:38:16Z","timestamp":1775083096180,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":16,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819548385","type":"print"},{"value":"9789819548392","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-4839-2_19","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:37:51Z","timestamp":1767317871000},"page":"251-261","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An LP-Rounding Based Algorithm for\u00a0Hard Capacitated Uniform Facility Location Problem with\u00a0Soft Penalties"],"prefix":"10.1007","author":[{"given":"Hanyin","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruiqing","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhikang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"issue":"1","key":"19_CR1","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":"19_CR2","doi-asserted-by":"publisher","unstructured":"Charikar, M., Khuller, S., Mount, D.M., Narasimhan, G.: Algorithms for facility location problems with outliers (extended abstract). In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete algorithms of the Conference, Washington D.C., USA (2001). https:\/\/doi.org\/10.5555\/365411.365555","DOI":"10.5555\/365411.365555"},{"key":"19_CR3","doi-asserted-by":"publisher","unstructured":"Dabas, R., Garg, N., Gupta, N.: Capacitated facility location with outliers and uniform facility costs. In: Proceedings of International Conference on Integer Programming and Combinatorial Optimization of the Conference, Wroc\u0142aw, Poland (2024). https:\/\/doi.org\/10.1007\/978-3-031-59835-7_7","DOI":"10.1007\/978-3-031-59835-7_7"},{"key":"19_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2022.100723","volume":"45","author":"S Grover","year":"2022","unstructured":"Grover, S., Gupta, N., Khuller, S.: LP-based approximation for uniform capacitated facility location problem. Discret. Optim. 45, 100723 (2022)","journal-title":"Discret. Optim."},{"key":"19_CR5","doi-asserted-by":"publisher","unstructured":"Kao, M.J. Improved approximation algorithm for capacitated facility location with uniform facility cost. In: Proceedings of the 34th International Symposium on Algorithms and Computation of the Conference, Kyoto, Japan (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2023.45","DOI":"10.4230\/LIPIcs.ISAAC.2023.45"},{"key":"19_CR6","doi-asserted-by":"publisher","unstructured":"Kao, M.J.: On the integrality gap of MFN relaxation for the capacitated facility location problem. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms of the Conference, Florence, Italy (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch40","DOI":"10.1137\/1.9781611977554.ch40"},{"issue":"1","key":"19_CR7","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-010-0380-8","volume":"131","author":"R Levi","year":"2012","unstructured":"Levi, R., Shmoys, D.B., Swamy, C.: LP-based approximation algorithms for capacitated facility location. Math. Program. 131(1), 365\u2013379 (2012)","journal-title":"Math. Program."},{"key":"19_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"},{"issue":"3","key":"19_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1017\/S0960129524000124","volume":"34","author":"X Liu","year":"2024","unstructured":"Liu, X., Li, W.: An approximation algorithm for the-prize-collecting multicut problem in trees with submodular penalties. Math. Struct. Comput. Sci. 34(3), 193\u2013210 (2024)","journal-title":"Math. Struct. Comput. Sci."},{"issue":"3","key":"19_CR10","doi-asserted-by":"publisher","first-page":"1964","DOI":"10.1007\/s10878-020-00568-2","volume":"44","author":"X Liu","year":"2022","unstructured":"Liu, X., Li, W.: Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties. J. Comb. Optim. 44(3), 1964\u20131976 (2022)","journal-title":"J. Comb. Optim."},{"issue":"6","key":"19_CR11","doi-asserted-by":"publisher","first-page":"2165","DOI":"10.1007\/s11590-021-01724-1","volume":"15","author":"X Liu","year":"2021","unstructured":"Liu, X., Li, W.: Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optim. Lett. 15(6), 2165\u20132180 (2021). https:\/\/doi.org\/10.1007\/s11590-021-01724-1","journal-title":"Optim. Lett."},{"issue":"6","key":"19_CR12","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1360\/SSI-2021-0445","volume":"52","author":"X Liu","year":"2022","unstructured":"Liu, X., Dai, H., Li, S., Li, W.: The k-prize-collecting minimum power cover problem with submodular penalties on a plane. Sci. Sin. Inform 52(6), 947\u2013959 (2022)","journal-title":"Sci. Sin. Inform"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/j.tcs.2022.05.012","volume":"923","author":"X Liu","year":"2022","unstructured":"Liu, X., Li, W., Dai, H.: Approximation algorithms for the minimum power cover problem with submodular\/linear penalties. Theoret. Comput. Sci. 923, 256\u2013270 (2022)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"19_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.26599\/TST.2024.9010040","volume":"30","author":"R Miao","year":"2024","unstructured":"Miao, R., Wu, C., Yuan, J.: LP-rounding based algorithm for capacitated uniform facility location problem with soft penalties. Tsinghua Sci. Technol. 30(1), 279\u2013289 (2024)","journal-title":"Tsinghua Sci. Technol."},{"issue":"7","key":"19_CR15","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.3390\/math13071023","volume":"13","author":"H Xiao","year":"2025","unstructured":"Xiao, H., Zhang, J., Zhang, Z., Li, W.: A survey of approximation algorithms for the universal facility location problem. Mathematics 13(7), 1023 (2025)","journal-title":"Mathematics"},{"issue":"4","key":"19_CR16","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(4), 424\u201336 (2009)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-4839-2_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:37:52Z","timestamp":1767317872000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-4839-2_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819548385","9789819548392"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-4839-2_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jinan","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.maths.sdnu.edu.cn\/TAMC2025.htm","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}