Improved approximation for directed cut problems

We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n 1/2 ). We obtain an Õ(n 11/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 Õ(n 11/23 ) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.

Authors

• Amit Agarwal
• Noga Alon
• Moses Charikar

Keywords

• approximation algorithm
• directed multicut
• directed sparsest cut
• linear programming relaxation