{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T22:38:17Z","timestamp":1775083097402,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":22,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819683116","type":"print"},{"value":"9789819683123","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[[2025]]},"DOI":"10.1007\/978-981-96-8312-3_15","type":"book-chapter","created":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:55:43Z","timestamp":1751284543000},"page":"193-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An LP-Rounding Based Algorithm for\u00a0Soft Capacitated Facility Location Problem with\u00a0Submodular Penalties"],"prefix":"10.1007","author":[{"given":"Hanyin","family":"Xiao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaming","family":"Zhang","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":[[2025,6,30]]},"reference":[{"issue":"1","key":"15_CR1","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1051\/ro:2007011","volume":"41","author":"L Alfandari","year":"2007","unstructured":"Alfandari, L.: Improved approximation of the general soft-capacitated facility location problem. RAIRO Oper. Res. 41(1), 83\u201393 (2007)","journal-title":"RAIRO Oper. Res."},{"key":"15_CR2","doi-asserted-by":"publisher","unstructured":"Arya, V., Garg, N., Khandekar, R., et al.: Local search heuristic for k-median and facility location problems. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing. STOC 2001, pp. 21\u201329 Association for Computing Machinery, New York, NY, USA (2001). https:\/\/doi.org\/10.1145\/380752.380755","DOI":"10.1145\/380752.380755"},{"key":"15_CR3","doi-asserted-by":"publisher","unstructured":"Chudak, F.A.; Shmoys, D.B. Improved approximation algorithms for the capacitated facility location problem. In: Proceedings of the 10th Annual ACM-SIAM symposium on Discrete algorithms. SODA 1999, pp. 875\u2013876 Baltimore, MD, USA (1999). https:\/\/doi.org\/10.5555\/314500.315061","DOI":"10.5555\/314500.315061"},{"key":"15_CR4","doi-asserted-by":"publisher","unstructured":"Chudak, F. A., Nagano, K.: Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lov\u00e1sz extension and non-smooth convex optimization. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2007, pp. 79\u201388 Society for Industrial and Applied Mathematics, USA (2007). https:\/\/doi.org\/10.5555\/1283383.1283393","DOI":"10.5555\/1283383.1283393"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D Du","year":"2012","unstructured":"Du, D., Lu, R., Xu, D.: A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63, 191\u2013200 (2012)","journal-title":"Algorithmica"},{"key":"15_CR6","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., Miyazawa, F.K., Pedrosa, L.: 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":"15_CR7","unstructured":"Fujishige, S.: Submodular Functions and Optimization, vol. 58. Elsevier (2005)"},{"key":"15_CR8","doi-asserted-by":"publisher","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 2005, vol. 5, pp. 933\u2013942 Society for Industrial and Applied Mathematics, USA (2005). https:\/\/doi.org\/10.5555\/1070432.1070567","DOI":"10.5555\/1070432.1070567"},{"key":"15_CR9","doi-asserted-by":"publisher","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing. STOC 2002, pp. 731\u2013740 Association for Computing Machinery, New York, NY, USA (2002). https:\/\/doi.org\/10.1145\/509907.510012","DOI":"10.1145\/509907.510012"},{"issue":"2","key":"15_CR10","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":"15_CR11","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":"15_CR12","doi-asserted-by":"crossref","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45\u201358 (2013)","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"15_CR13","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":"15_CR14","doi-asserted-by":"crossref","unstructured":"Li, Y., Du, D., Xiu, N., et al.: A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties. Theor. Comput. Sci. 476, 109\u2013117 (2013)","DOI":"10.1016\/j.tcs.2012.11.037"},{"issue":"3","key":"15_CR15","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":"15_CR16","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":"15_CR17","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":"15_CR18","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. SCIENTIA SINICA Informationis 52(6), 947\u2013959 (2022)","journal-title":"SCIENTIA SINICA Informationis"},{"key":"15_CR19","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."},{"key":"15_CR20","doi-asserted-by":"publisher","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Jansen, K., Leonardi, S., Vazirani, V. (eds.) APPROX 2002. LNCS, vol. 2462, pp. 229\u2013242. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45753-4_20","DOI":"10.1007\/3-540-45753-4_20"},{"key":"15_CR21","doi-asserted-by":"publisher","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-Approximation algorithm for the soft-capacitated facility location problem. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2003 2003. LNCS, vol. 2764. Springer, Berlin, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45198-3_12","DOI":"10.1007\/978-3-540-45198-3_12"},{"issue":"7","key":"15_CR22","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"}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-8312-3_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T12:33:31Z","timestamp":1751286811000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-8312-3_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819683116","9789819683123"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-8312-3_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"30 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","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":"30 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 July 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":"faw2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ijtcs-faw.github.io\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}