{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T08:29:08Z","timestamp":1725697748767},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,11,14]],"date-time":"2020-11-14T00:00:00Z","timestamp":1605312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,14]],"date-time":"2020-11-14T00:00:00Z","timestamp":1605312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11590-020-01665-1","type":"journal-article","created":{"date-parts":[[2020,11,14]],"date-time":"2020-11-14T00:04:56Z","timestamp":1605312296000},"page":"1105-1112","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An approximation algorithm for the submodular multicut problem in trees with linear penalties"],"prefix":"10.1007","volume":"15","author":[{"given":"Chenfei","family":"Hou","sequence":"first","affiliation":[]},{"given":"Suogang","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Wen","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]},{"given":"Bo","family":"Hou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,14]]},"reference":[{"key":"1665_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"2","key":"1665_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"2006","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (2006)","journal-title":"SIAM J. Comput."},{"key":"1665_CR3","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"1665_CR4","doi-asserted-by":"crossref","unstructured":"Iwata, S., Nagano, K.: Submodular function minimization under covering constraints, In: The 50th annual symposium on foundations of computer science, FOCS, pp. 671\u2013680 (2009)","DOI":"10.1109\/FOCS.2009.31"},{"key":"1665_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2016.10.017","volume":"659","author":"N Kamiyama","year":"2017","unstructured":"Kamiyama, N.: A note on the submodular vertex cover problem with submodular penalties. Theor. Comput. Sci. 659, 95\u201397 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"1665_CR6","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1016\/j.tcs.2006.09.018","volume":"369","author":"A Levin","year":"2006","unstructured":"Levin, A., Segev, D.: Partial multicuts in trees. Theor. Comput. Sci. 369(1\u20133), 384\u2013395 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"1665_CR7","doi-asserted-by":"crossref","unstructured":"Liu, X.F., Li, W.D.: A primal dual approximation algorithm for the multicut problem in trees with submodular penalties, In: International Conference on Algorithmic Applications in Management, pp. 203\u2013211 (2019)","DOI":"10.1007\/978-3-030-27195-4_19"},{"key":"1665_CR8","first-page":"235","volume-title":"Mathematical Programing the State of the Art","author":"L Lov\u00e1sz","year":"1983","unstructured":"Lov\u00e1sz, L.: Submodular Functions and Convexity. In: Bachm, A., Grtschel, M., Korte, B. (eds.) Mathematical Programing the State of the Art, pp. 235\u2013237. Springer, Berlin (1983)"},{"key":"1665_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.tcs.2016.04.005","volume":"630","author":"DC Xu","year":"2016","unstructured":"Xu, D.C., Wang, F.M., Du, D.L., Wu, C.C.: Approximation algorithms for submodular vertex cover problems with linear\/submodular penalties using primal-dual technique. Theor. Comput. Sci. 630, 117\u2013125 (2016)","journal-title":"Theor. Comput. Sci."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01665-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-020-01665-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-020-01665-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T19:12:54Z","timestamp":1620414774000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-020-01665-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,14]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["1665"],"URL":"https:\/\/doi.org\/10.1007\/s11590-020-01665-1","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,14]]},"assertion":[{"value":"11 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}