{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T22:46:36Z","timestamp":1777502796551,"version":"3.51.4"},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T00:00:00Z","timestamp":1713312000000},"content-version":"unspecified","delay-in-days":47,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,3]]},"abstract":"Abstract<\/jats:title>Let \n$T=(V,E)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be a tree in which each edge is assigned a cost; let \n$\\mathcal{P}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> be a set of source\u2013sink pairs of vertices in V<\/jats:italic> in which each source\u2013sink pair produces a profit. Given a lower bound K<\/jats:italic> for the profit, the K<\/jats:italic>-prize-collecting multicut problem in trees with submodular penalties is to determine a partial multicut \n$M\\subseteq E$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that the total profit of the disconnected pairs after removing M<\/jats:italic> from T<\/jats:italic> is at least K<\/jats:italic>, and the total cost of edges in M<\/jats:italic> plus the penalty of the set of still-connected pairs is minimized, where the penalty is determined by a nondecreasing submodular function. Based on the primal-dual scheme, we present a combinatorial polynomial-time algorithm by carefully increasing the penalty. In the theoretical analysis, we prove that the approximation factor of the proposed algorithm is \n$(\\frac{8}{3}+\\frac{4}{3}\\kappa+\\varepsilon)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, where \n$\\kappa$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the total curvature of the submodular function and \n$\\varepsilon$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is any fixed positive number. Experiments reveal that the objective value of the solutions generated by the proposed algorithm is less than 130% compared with that of the optimal value in most cases.<\/jats:p>","DOI":"10.1017\/s0960129524000124","type":"journal-article","created":{"date-parts":[[2024,4,17]],"date-time":"2024-04-17T07:46:52Z","timestamp":1713340012000},"page":"193-210","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":10,"title":["An approximation algorithm for the -prize-collecting multicut problem in trees with submodular penalties"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1650-2625","authenticated-orcid":false,"given":"Xiaofei","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weidong","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,4,17]]},"reference":[{"key":"S0960129524000124_ref3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","article-title":"Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the rado-edmonds theorem","volume":"7","author":"Conforti","year":"1984","journal-title":"Discrete Applied Mathematics"},{"key":"S0960129524000124_ref27","doi-asserted-by":"crossref","unstructured":"Yang, R. , Xu, D. , Cheng, Y. , Gao, C. and Du, D.-Z. (2019). Streaming submodular maximization under noises. In: 39th IEEE International Conference on Distributed Computing Systems (ICDCS 2019), IEEE, 348\u2013357.","DOI":"10.1109\/ICDCS.2019.00042"},{"key":"S0960129524000124_ref11","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/opre.11.3.344","article-title":"Multi-commodity network flows","volume":"11","author":"Hu","year":"1963","journal-title":"Operations Research"},{"key":"S0960129524000124_ref19","first-page":"1","article-title":"The B-prize-collecting multicut problem in paths, spider graphs and rings","volume":"2023","author":"Liu","year":"2023","journal-title":"International Journal of Foundations of Computer Science"},{"key":"S0960129524000124_ref13","doi-asserted-by":"crossref","unstructured":"Keuper, M. , Andres, B. and & Brox, T. (2015). Motion trajectory segmentation via minimum cost multicuts. In: 2015 IEEE International Conference on Computer Vision (ICCV 2015), IEEE, 3271\u20133279.","DOI":"10.1109\/ICCV.2015.374"},{"key":"S0960129524000124_ref10","first-page":"207","article-title":"An approximation algorithm for P-prize-collecting set cover problem","volume":"11","author":"Guo","year":"2023","journal-title":"Journal of the Operations Research Society of China"},{"key":"S0960129524000124_ref18","doi-asserted-by":"crossref","first-page":"1964","DOI":"10.1007\/s10878-020-00568-2","article-title":"Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties","volume":"44","author":"Liu","year":"2022","journal-title":"Journal of Combinatorial Optimization"},{"key":"S0960129524000124_ref16","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/j.tcs.2006.09.018","article-title":"Partial multicuts in trees","volume":"369","author":"Levin","year":"2006","journal-title":"Theoretical Computer Science"},{"key":"S0960129524000124_ref14","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","article-title":"Vertex cover might be hard to approximate to with \n\n\n\n$2-\\varepsilon$","volume":"74","author":"Khot","year":"2008","journal-title":"Journal of Computer and System Sciences"},{"key":"S0960129524000124_ref29","doi-asserted-by":"crossref","first-page":"161402","DOI":"10.1007\/s11704-020-0368-3","article-title":"The LP-rounding plus greed approach for partial optimization revisited","volume":"16","author":"Zhang","year":"2022","journal-title":"Frontiers of Computer Science"},{"key":"S0960129524000124_ref12","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1016\/j.tcs.2020.07.014","article-title":"An approximation algorithm for the k-prize-collecting multicut on a tree problem","volume":"844","author":"Hou","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"S0960129524000124_ref26","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.tcs.2016.04.005","article-title":"Approximation algorithms for submodular vertex cover problems with linear\/submodular penalties using primal-dual technique","volume":"630","author":"Xu","year":"2016","journal-title":"Theoretical Computer Science"},{"key":"S0960129524000124_ref23","doi-asserted-by":"crossref","first-page":"3522","DOI":"10.1007\/s00453-021-00919-3","article-title":"A 2-approximation for the k-prize-collecting steiner tree problem","volume":"84","author":"Pedrosa","year":"2022","journal-title":"Algorithmica"},{"key":"S0960129524000124_ref15","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","article-title":"A unified approach to approximating partial covering problems","volume":"59","author":"K\u00f6nemann","year":"2011","journal-title":"Algorithmica"},{"key":"S0960129524000124_ref30","doi-asserted-by":"crossref","first-page":"1240","DOI":"10.1016\/j.dam.2012.01.016","article-title":"An approximation algorithm for the generalized k-multicut problem","volume":"160","author":"Zhang","year":"2012","journal-title":"Discrete Applied Mathematics"},{"key":"S0960129524000124_ref20","doi-asserted-by":"crossref","first-page":"173404","DOI":"10.1007\/s11704-022-1665-9","article-title":"A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties","volume":"17","author":"Liu","year":"2022","journal-title":"Frontiers of Computer Science"},{"key":"S0960129524000124_ref9","doi-asserted-by":"crossref","unstructured":"Golovin, D. , Nagarajan, V. and Singh, M. (2006). Approximating the k-multicut problem. In: 2006 ACM-SIAM Symposium on Discrete Algorithms (SODA 2006). SIAM, 621\u2013630.","DOI":"10.1145\/1109557.1109625"},{"key":"S0960129524000124_ref28","doi-asserted-by":"crossref","unstructured":"Yannakakis, M. , Kanellakis, P. C. , Cosmadakis, S. S. and Papadimitriou, C. H. (1983). Cutting and partitioning a graph after a fixed pattern. In: 1983 International Colloquium on Automata, Languages and Programming (ICALP 1983), Springer, 712\u2013722.","DOI":"10.1007\/BFb0036950"},{"key":"S0960129524000124_ref4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","article-title":"Minimal multicut and maximal integer multiflow: A survey","volume":"162","author":"Costa","year":"2005","journal-title":"European Journal of Operational Research"},{"key":"S0960129524000124_ref25","doi-asserted-by":"crossref","unstructured":"Tang, S. , Andriluka, M. , Andres, B. and Schiele, B. (2017). Multiple people tracking by lifted multicut and person re-identification. In: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2017), IEEE, 3701\u20133710.","DOI":"10.1109\/CVPR.2017.394"},{"key":"S0960129524000124_ref1","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.tcs.2019.12.015","article-title":"Complexity of the multicut problem, in its vanilla, partial and generalized versions, in graphs of bounded treewidth","volume":"809","author":"Bentz","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"S0960129524000124_ref24","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1017\/S0960129521000104","article-title":"An improved primal-dual approximation algorithm for the k-means problem with penalties","volume":"32","author":"Ren","year":"2022","journal-title":"Mathematical Structures in Computer Science"},{"key":"S0960129524000124_ref22","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/s10107-007-0189-2","article-title":"A faster strongly polynomial time algorithm for submodular function minimization","volume":"118","author":"Orlin","year":"2009","journal-title":"Mathematical Programming"},{"key":"S0960129524000124_ref7","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/S0097539793243016","article-title":"Approximate max-flow min-(multi)cut theorems and their applications","volume":"25","author":"Garg","year":"1996","journal-title":"SIAM Journal on Computing"},{"key":"S0960129524000124_ref17","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","article-title":"Improved approximation algorithms for the facility location problems with linear\/submodular penalties","volume":"73","author":"Li","year":"2015","journal-title":"Algorithmica"},{"key":"S0960129524000124_ref6","volume-title":"Submodular Functions and Optimization","author":"Fujishige","year":"2005"},{"key":"S0960129524000124_ref5","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","article-title":"The complexity of multiterminal cuts","volume":"23","author":"Dahlhaus","year":"1994","journal-title":"SIAM Journal on Computing"},{"key":"S0960129524000124_ref21","unstructured":"Mestre, J. (2008). Lagrangian relaxation and partial cover problem. In: 2008 International Symposium on Theoretical Aspects of Computer Science (STACS 2008), LIPIcs, 539\u2013550."},{"key":"S0960129524000124_ref8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","article-title":"Primal-dual approximation algorithms for integral flow and multicut in trees","volume":"18","author":"Garg","year":"1997","journal-title":"Algorithmica"},{"key":"S0960129524000124_ref2","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","article-title":"On the hardness of approximating multicut and sparsest-cut","volume":"15","author":"Chawla","year":"2006","journal-title":"Computational Complexity"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T11:02:03Z","timestamp":1717412523000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000124\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S0960129524000124"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000124","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}