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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2012

הערה ביבליוגרפית

Funding Information:
E-mail addresses: moranfe@cs.technion.ac.il (M. Feldman), guyk@camden.rutgers.edu (G. Kortsarz), nutov@openu.ac.il (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'. יחד הם יוצרים טביעת אצבע ייחודית.

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