{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T12:14:41Z","timestamp":1790856881634,"version":"4.1.0"},"reference-count":7,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>\n                    A directed multiway cut separates a set of terminals T={s\n                    <jats:sub>1<\/jats:sub>\n                    , . . . , s\n                    <jats:sub>k<\/jats:sub>\n                    } in a directed capacitated graph G=(V,E). Finding a minimum directed multiway cut is an NP-hard problem. We give a polynomial-time algorithm that achieves an approximation factor of 2 for this problem. This improves the result of Garg, Vazirani, and Yannakakis [Proceedings of the 21st International Colloquium on Automata, Languages, and Programming, Jerusalem, Israel, 1994, pp. 487--498], who gave an algorithm that achieves an approximation factor of 2 log k. Our approximation algorithm uses a novel technique for relaxing a multiway flow function in order to find a directed multiway cut. It also implies that the integrality gap of the linear program for the directed multiway cut problem is at most 2.\n                  <\/jats:p>","DOI":"10.1137\/s009753979732147x","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"477-482","source":"Crossref","is-referenced-by-count":24,"title":["A 2-Approximation Algorithm for the Directed Multiway Cut Problem"],"prefix":"10.1137","volume":"31","author":[{"given":"Joseph (Seffi)","family":"Naor","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonid","family":"Zosin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798340047"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, and M. Yannakakis,\n                      Multiway cuts in directed and node weighted graphs\n                      , in Proceedings of the 21st International Colloquium on Automata, Languages, and Programming, 1994, Jerusalem, Israel, pp. 487\u2013498.","DOI":"10.1007\/3-540-58201-0_92"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"David Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal Young, Rounding algorithms for a geometric embedding of minimum multiway cut, ACM, New York, 1999, 668\u20136781798090","DOI":"10.1145\/301250.301430"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"J. Naor and L. Zosin,\n                      A 2\u2010approximation algorithm for the directed multiway cut problem\n                      , in Proceedings of the 38th IEEE Conference on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 548\u2013553.","DOI":"10.1109\/SFCS.1997.646144"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753979732147X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:27Z","timestamp":1787336487000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753979732147X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":7,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S009753979732147X"],"URL":"https:\/\/doi.org\/10.1137\/s009753979732147x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}