{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T11:59:21Z","timestamp":1775044761625,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T00:00:00Z","timestamp":1775001600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Scientific Research Fund Project of Yunnan Education Department","award":["No. 2026Y0147"],"award-info":[{"award-number":["No. 2026Y0147"]}]},{"name":"Innovation Project of Postgraduate Students in the Academic Degree of Yunnan University","award":["No. KC-252511650"],"award-info":[{"award-number":["No. KC-252511650"]}]},{"name":"Yunnan Fundamental Research Projects","award":["No. 202501AS070076"],"award-info":[{"award-number":["No. 202501AS070076"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00224-026-10271-0","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:44:25Z","timestamp":1775040265000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Lp-rounding Based Algorithm for Soft Capacitated Facility Location Problem with Submodular Penalties"],"prefix":"10.1007","volume":"70","author":[{"given":"Hanyin","family":"Xiao","sequence":"first","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,4,1]]},"reference":[{"issue":"1","key":"10271_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":"10271_CR2","unstructured":"Rahbari, A., Nasiri, M. M.: Capacitated Competitive Facility Location Problem. figshare. Dataset, (2018)"},{"key":"10271_CR3","doi-asserted-by":"crossref","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristic for $$k$$-median and facility location problems. In: Proceedings of the 33rd annual ACM Symposium on Theory of Computing, pp. 21\u201329 (2001)","DOI":"10.1145\/380752.380755"},{"issue":"6","key":"10271_CR4","doi-asserted-by":"publisher","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(6), 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"key":"10271_CR5","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":"10271_CR6","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34, 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"10271_CR7","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 18th annual ACM-SIAM Symposium on Discrete Algorithms, pp. 79\u201388 (2007)"},{"issue":"1","key":"10271_CR8","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(1), 191\u2013200 (2012)","journal-title":"Algorithmica"},{"issue":"4","key":"10271_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"10271_CR10","doi-asserted-by":"crossref","unstructured":"Feng, C., Liu, W., Zhang, G., Hou, B.: Approximation Algorithm for $$k$$-Product Uncapacitated Facility Location Problem with Submodular Penalties. Theoret. Comput. Sci. 115785 (2026)","DOI":"10.1016\/j.tcs.2026.115785"},{"key":"10271_CR11","unstructured":"Fujishige, S.: Submodular functions and optimization. Elsevier, 2005"},{"issue":"1","key":"10271_CR12","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":"3","key":"10271_CR13","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1007\/s10878-020-00631-y","volume":"40","author":"L Han","year":"2020","unstructured":"Han, L., Xu, D., Xu, Y., Zhang, D.: Approximating the $$\\tau $$-relaxed soft capacitated facility location problem. J. Comb. Optim. 40(3), 848\u2013860 (2020)","journal-title":"J. Comb. Optim."},{"key":"10271_CR14","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: Proceedings of the 16th annual ACM-SIAM Symposium on Discrete Algorithms, pp. 933\u2013942 (2005)"},{"issue":"1","key":"10271_CR15","doi-asserted-by":"publisher","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(1), 148\u2013162 (1982)","journal-title":"Math. Program."},{"issue":"2","key":"10271_CR16","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"},{"key":"10271_CR17","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"},{"issue":"4","key":"10271_CR18","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"AA Kuehn","year":"1963","unstructured":"Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manage. Sci. 9(4), 643\u2013666 (1963)","journal-title":"Manage. Sci."},{"issue":"1","key":"10271_CR19","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":"10271_CR20","doi-asserted-by":"crossref","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Computat. 222, 45\u201358 (2013)","DOI":"10.1016\/j.ic.2012.01.007"},{"key":"10271_CR21","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2012.11.037","volume":"476","author":"Y Li","year":"2013","unstructured":"Li, Y., Du, D., Xiu, N., Xu, D.: A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties. Theoret. Comput. Sci. 476, 109\u2013117 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"10271_CR22","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(2), 460\u2013482 (2015)","journal-title":"Algorithmica"},{"key":"10271_CR23","doi-asserted-by":"crossref","unstructured":"Lin, J.H., Vitter, J.S.: $$e$$-Approximations with minimum packing constraint violation. In: Proceedings of the 24th annual ACM Symposium on Theory of Computing pp. 771\u2013782 (1992)","DOI":"10.1145\/129712.129787"},{"issue":"2","key":"10271_CR24","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","volume":"11","author":"AS Manne","year":"1964","unstructured":"Manne, A.S.: Plant location under economies-of-scale\u2013decentralization and computation. Manage. Sci. 11(2), 213\u2013235 (1964)","journal-title":"Manage. Sci."},{"key":"10271_CR25","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 229\u2013242 (2002)","DOI":"10.1007\/3-540-45753-4_20"},{"key":"10271_CR26","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of the 7th International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 129\u2013140 (2003)","DOI":"10.1007\/978-3-540-45198-3_12"},{"issue":"1","key":"10271_CR27","doi-asserted-by":"publisher","first-page":"279","DOI":"10.26599\/TST.2024.9010040","volume":"30","author":"R Miao","year":"2025","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 (2025)","journal-title":"Tsinghua Sci. Technol."},{"key":"10271_CR28","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"},{"issue":"1","key":"10271_CR29","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1287\/opre.1040.0140","volume":"53","author":"J Shu","year":"2005","unstructured":"Shu, J., Teo, C.P., Shen, Z.J.M.: Stochastic transportation-inventory network design problem. Oper. Res. 53(1), 48\u201360 (2005)","journal-title":"Oper. Res."},{"issue":"3","key":"10271_CR30","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1287\/opre.1030.0096","volume":"52","author":"CP Teo","year":"2004","unstructured":"Teo, C.P., Shu, J.: Warehouse-retailer network design problem. Oper. Res. 52(3), 396\u2013408 (2004)","journal-title":"Oper. Res."},{"issue":"6","key":"10271_CR31","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1080\/02331934.2013.840626","volume":"63","author":"C Wu","year":"2014","unstructured":"Wu, C., Du, D., Xu, D.: A per-scenario bound for the two-stage stochastic facility location problem with linear penalty. Optimization 63(6), 921\u2013930 (2014)","journal-title":"Optimization"},{"key":"10271_CR32","doi-asserted-by":"crossref","unstructured":"Xiao, H., Sun, R., Zhang, Z., Li, W.: An LP-rounding based algorithm for hard capacitated uniform facility location problem with soft penalties. In: Proceedings of annual conference on Theory and Applications of Models of Computation, pp. 251\u2013261 (2025)","DOI":"10.1007\/978-981-95-4839-2_19"},{"key":"10271_CR33","doi-asserted-by":"crossref","unstructured":"Xiao, H., Zhang, J., Zhang, Z., Li, W.: An LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties. In: Proceedings of International Workshop on Frontiers in Algorithmics, pp. 193\u2013206 (2025)","DOI":"10.1007\/978-981-96-8312-3_15"},{"issue":"7","key":"10271_CR34","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":"3","key":"10271_CR35","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(3), 119\u2013123 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"10271_CR36","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\u2013436 (2009)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"10271_CR37","first-page":"617","volume":"64","author":"D Xu","year":"2015","unstructured":"Xu, D., Gao, D., Wu, C.: A primal-dual 3-approximation algorithm for the stochastic facility location problem with submodular penalties. Optimization 64(3), 617\u2013626 (2015)","journal-title":"Optimization"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10271-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10271-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10271-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:44:28Z","timestamp":1775040268000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10271-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10271"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10271-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,1]]},"assertion":[{"value":"19 November 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"22"}}