{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:34Z","timestamp":1750220974258,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T00:00:00Z","timestamp":1545264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JSPS KAKENHI","award":["JP25280004, JP26330023, JP26280004, and JP17K00029"],"award-info":[{"award-number":["JP25280004, JP26330023, JP26280004, and JP17K00029"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            In this article, we develop an\n            <jats:italic>O<\/jats:italic>\n            ((\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            )MSF(\n            <jats:italic>n,m<\/jats:italic>\n            ,1))-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with\n            <jats:italic>n<\/jats:italic>\n            nodes,\n            <jats:italic>m<\/jats:italic>\n            edges, and\n            <jats:italic>k<\/jats:italic>\n            terminals, where MSF(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            ,\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            ,\u03b3) denotes the time complexity of solving the maximum submodular flow problem in a network with\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            nodes,\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>\u2032<\/jats:sup>\n            edges, and the complexity \u03b3 of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            log\n            <jats:italic>k<\/jats:italic>\n            ) time. This is the first combinatorial strongly polynomial time algorithm for this problem. Our algorithm is built on a developing theory of discrete convex functions on certain graph structures. Applications include \u201cellipsoid-free\u201d combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.\n          <\/jats:p>","DOI":"10.1145\/3291531","type":"journal-article","created":{"date-parts":[[2018,12,20]],"date-time":"2018-12-20T13:35:46Z","timestamp":1545312946000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Dual Descent Algorithm for Node-capacitated Multiflow Problems and Its Applications"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4784-5110","authenticated-orcid":false,"given":"Hiroshi","family":"Hirai","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,12,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.40.437"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9141-y"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Faster algorithms for half-integral T-path packing. In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC\u201917)","volume":"92","author":"Babenko M. A.","year":"2017","journal-title":"LIPIcs"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_11"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9377-3"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","author":"Chekuri C.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-008-2157-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.24.4.628"},{"volume-title":"Connections in Combinatorial Optimization","author":"Frank A.","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","DOI":"10.1016\/j.dam.2011.09.003"},{"edition":"2","volume-title":"Submodular Functions and Optimization","author":"Fujishige S.","key":"e_1_2_1_10_1"},{"key":"e_1_2_1_11_1","first-page":"322","article-title":"Algorithms for submodular flows","volume":"83","author":"Fujishige S.","year":"2000","journal-title":"IEICE Trans. Inf. Syst."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03167272"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00111-1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446232"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01261321"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0506-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0824-7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2015.07.001"},{"volume-title":"Communications of NII Shonan Meetings, T. Fukunaga and K. Kawarabayashi (Eds.)","year":"2017","author":"Hirai H.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.61.71"},{"volume-title":"Combinatorial Methods for Flow Problems","author":"Karzanov A. V.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581152"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"W. Mader. 1978\/79. \u00dcber die Maximalzahl kreuzungsfreier H-Wege. Archiv Math. 31 (1978\/79) 387--402.  W. Mader. 1978\/79. \u00dcber die Maximalzahl kreuzungsfreier H -Wege. Archiv Math. 31 (1978\/79) 387--402.","DOI":"10.1007\/BF01226465"},{"volume-title":"Discrete Convex Analysis","author":"Murota K.","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718508"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2014.06.005"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250878"},{"volume-title":"Combinatorial Optimization\u2014Polyhedra and Efficiency","author":"Schrijver A.","key":"e_1_2_1_28_1"},{"volume-title":"Approximation Algorithms","author":"Vazirani V. V.","key":"e_1_2_1_29_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04565-7"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3291531","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3291531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3291531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,20]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3291531"],"URL":"https:\/\/doi.org\/10.1145\/3291531","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,12,20]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}