Loading...
Please wait, while we are loading the content...
Similar Documents
Improved approximation for directed cut problems (2007)
| Content Provider | CiteSeerX |
|---|---|
| Author | Agarwal, Amit Alon, Noga Charikar, Moses |
| Abstract | 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 Õ(n11/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 Õ(n11/23) upper bound on the ratio between the maximum multicommodity flow and minimum multicut in directed graphs. |
| File Format | |
| Publisher Date | 2007-01-01 |
| Access Restriction | Open |
| Subject Keyword | Natural Lp Relaxation Known Approximation Ratio Directed Cut Problem Maximum Multicommodity Flow Improved Approximation Algorithm Minimum Multicut Randomized Rounding Algorithm Directed Multicut |
| Content Type | Text |
