Improved approximation 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×V of ordered node pairs, and an integer k≤|D|, find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs (s,t) D. When k=|D|, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: Õ(k2/3) for k-DSF by Charikar et al. (1999) [6], and O(k1/2+ε) for DSF by Chekuri et al. (2008) [7]. Our main result is achieving the first sub-linear in terms of n=|V| approximation ratio for DSF. Specifically, we give an O(.min{n4/5,m2 /3})-approximation scheme for DSF. For k-DSF we give a simple greedy O(k1/2+ε)-approximation algorithm. This improves upon the best known ratio Õ(k2/3) by Charikar et al. (1999) [6], and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 [18]). This algorithm uses a new structure called start-junction tree which may be of independent interest.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)279-292
عدد الصفحات14
دوريةJournal of Computer and System Sciences
مستوى الصوت78
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 2012

ملاحظة ببليوغرافية

Funding Information:
E-mail addresses: (M. Feldman), (G. Kortsarz), (Z. Nutov). 1 Part of this work was done as a part of author’s M.Sc. thesis at The Open University of Israel. 2 Partially supported by NSF support grant award number 0829959.


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

قم بذكر هذا