Improved approximating algorithms for Directed Steiner Forest

Moran Feldman, Guy Kortsarz, Zeev Nutov

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We consider the k-Directed Steiner Forest (k-DSF) problem: given a directed graph G = (V, E) with edge costs, a collection D ⊆ V x V of ordered node pairs, and an integer k ≤ |D|, find a min-cost subgraph H of G that contains an st-path for (at least) kc pairs (s, t) ∈ D. When k = |D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k 2/3) for k-DSF by Charikar et al. [2], and O(k 1/2+ε) for DSF by Chekuri et al. [3]. For DSF we give an O(n ε·mm{n 4/5, m 2/3})-approximation scheme using a novel LP-relaxation seeking to connect pairs via "cheap" paths. This is the first sublinear (in terms of n = |V|) approximation ratio for the problem. For k-DSF we give a simple greedy O(k 1/2+ε)-approximation scheme, improving the best known ratio Õ(k 2/3) by Charikar et al. [2], and (almost) matching, in terms of k, the best ratio known for the undirected variant [11]. Even when used for the particular case DSF, our algorithm favorably compares to the one of [3], which repeatedly solves linear programs, and uses complex time and space consuming transformations.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms
الصفحات922-931
عدد الصفحات10
حالة النشرنُشِر - 2009
الحدث20th Annual ACM-SIAM Symposium on Discrete Algorithms - New York, NY, الولايات المتّحدة
المدة: ٤ يناير ٢٠٠٩٦ يناير ٢٠٠٩

سلسلة المنشورات

الاسمProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

!!Conference

!!Conference20th Annual ACM-SIAM Symposium on Discrete Algorithms
الدولة/الإقليمالولايات المتّحدة
المدينةNew York, NY
المدة٤/٠١/٠٩٦/٠١/٠٩

بصمة

أدرس بدقة موضوعات البحث “Improved approximating algorithms for Directed Steiner Forest'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا