[ACM Press the thirty-ninth annual ACM symposium - San Diego, California, USA (2007.06.11-2007.06.13)] Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07 - Improved approximation for directed cut problems

✍ Scribed by Agarwal, Amit; Alon, Noga; Charikar, Moses S.

• Book ID: 121681950
• Publisher: ACM Press
• Year: 2007
• Weight: 265 KB
• Category: Article
• ISBN: 1595936319
• DOI: 10.1145/1250790.1250888

✦ Synopsis

We present improved approximation algorithms for directed multicut and directed sparsest cut. The current best known approximation ratio for these problems is O(n 1/2 ). We obtain an Õ(n 11/23 )-approximation. Our algorithm works with the natural LP relaxation used in prior work. We use a randomized rounding algorithm with a more sophisticated charging scheme and analysis to obtain our improvement. This also implies a Õ(n 11/23 ) upper bound on the ratio between the maximum multicommodity flow and minimum multicut in directed graphs.