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.