Greedy approximation algorithms for Directed Multicuts

Yana Kortsarts, Guy Kortsarz, Zeev Nutov

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


The Directed Multicut (DM) problem is: given a simple directed graph G = (V, E) with positive capacities u e on the edges, and a set K ⊆ V × V of ordered pairs of nodes of G, find a minimum capacity K-multicut; C ⊆ E is a K-multicut if in G - C there is no (s, t)-path for any (s, f) ε K. In the uncapacitated case (UDM) the goal is to find a minimum size K-multicut. The best approximation ratio known for DM is O(min{√n, opt}) by Gupta, where n = |V|, and opt is the optimal solution value. All known nontrivial approximation algorithms for the problem solve large linear programs. We give the first combinatorial approximation algorithms for the problem. Our main result is an Õ(n 2/3/opt 1/3|-approximation algorithm for UDM, which improves the Õ(min{opt, √n})-approximation for opt = Ω(n 1/2+ε). Combined with the article of Gupta, we get that UDM can be approximated within better than O(√n), unless opt = Θ̃(√n). We also give a simple and fast O(n 2/3)- approximation algorithm for DM.

שפה מקוריתאנגלית
עמודים (מ-עד)214-217
מספר עמודים4
כתב עתNetworks
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - יולי 2005

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Greedy approximation algorithms for Directed Multicuts'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי