A 2-approximation algorithm for the directed multiway cut problem

Authors
Citation
Js. Naor et L. Zosin, A 2-approximation algorithm for the directed multiway cut problem, SIAM J COMP, 31(2), 2001, pp. 477-482
Citations number
7
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
477 - 482
Database
ISI
SICI code
0097-5397(20011011)31:2<477:A2AFTD>2.0.ZU;2-C
Abstract
A directed multiway cut separates a set of terminals T = {s(1),...,s(k)} 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 achieve s an approximation factor of 2 for this problem. This improves the result o f Garg, Vazirani, and Yannakakis [ Proceedings of the 21st International Co lloquium on Automata, Languages, and Programming, Jerusalem, Israel, 1994, pp. 487-498], who gave an algorithm that achieves an approximation factor o f 2 log k. Our approximation algorithm uses a novel technique for relaxing a multiway ow function in order to nd a directed multiway cut. It also impl ies that the integrality gap of the linear program for the directed multiwa y cut problem is at most 2.