@inproceedings{8a3e64d18553422b8eef34c7c65822e7,
title = "Improved approximation for directed cut problems",
abstract = "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.",
keywords = "Approximation algorithm, Directed multicut, Directed sparsest cut, Linear programming relaxation",
author = "Amit Agarwal and Noga Alon and Charikar, \{Moses S.\}",
year = "2007",
doi = "10.1145/1250790.1250888",
language = "English (US)",
isbn = "1595936319",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
pages = "671--680",
booktitle = "STOC'07",
note = "STOC'07: 39th Annual ACM Symposium on Theory of Computing ; Conference date: 11-06-2007 Through 13-06-2007",
}