TY - GEN
T1 - Improved approximation for directed cut problems
AU - Agarwal, Amit
AU - Alon, Noga
AU - Charikar, Moses S.
PY - 2007
Y1 - 2007
N2 - We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n1/2). We obtain an (n11/23)-approximation. Our algorithm works with thenatural LP relaxation used in prior work. We use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. This also implies a (n11/23) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.
AB - We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n1/2). We obtain an (n11/23)-approximation. Our algorithm works with thenatural LP relaxation used in prior work. We use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. This also implies a (n11/23) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.
KW - Approximation algorithm
KW - Directed multicut
KW - Directed sparsest cut
KW - Linear programming relaxation
UR - http://www.scopus.com/inward/record.url?scp=35448973382&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35448973382&partnerID=8YFLogxK
U2 - 10.1145/1250790.1250888
DO - 10.1145/1250790.1250888
M3 - Conference contribution
AN - SCOPUS:35448973382
SN - 1595936319
SN - 9781595936318
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 671
EP - 680
BT - STOC'07
T2 - STOC'07: 39th Annual ACM Symposium on Theory of Computing
Y2 - 11 June 2007 through 13 June 2007
ER -