Name
Abstract | ||
|---|---|---|
We present an O(nlogn)-approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G=(V,E) with nonnegative edge lengths d:E-R^=^0 and a stretchk=1, a subgraph H=(V,E"H) is a k-spanner of G if for every edge (s,t)@?E, the graph H contains a path from s to t of length at most k@?d(s,t). The previous best approximation ratio was O@?(n^2^/^3), due to Dinitz and Krauthgamer (STOC @?11). We also improve the approximation ratio for the important special case of directed 3-spanners with unit edge lengths from O@?(n) to O(n^1^/^3logn). The best previously known algorithms for this problem are due to Berman, Raskhodnikova and Ruan (FSTTCS @?10) and Dinitz and Krauthgamer. The approximation ratio of our algorithm almost matches Dinitz and Krauthgamer@?s lower bound for the integrality gap of a natural linear programming relaxation. Our algorithm directly implies an O(n^1^/^3logn)-approximation for the 3-spanner problem on undirected graphs with unit lengths. An easy O(n)-approximation algorithm for this problem has been the best known for decades. Finally, we consider the Directed Steiner Forest problem: given a directed graph with edge costs and a collection of ordered vertex pairs, find a minimum-cost subgraph that contains a path between every prescribed pair. We obtain an approximation ratio of O(n^2^/^3^+^@e) for any constant @e0, which improves the O(n^@e@?min(n^4^/^5,m^2^/^3)) ratio due to Feldman, Kortsarz and Nutov (JCSS@?12). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.ic.2012.10.007 | Inf. Comput. |
Keywords | Field | DocType |
3-spanner problem,easy o,directed steiner forest problem,approximation ratio,original graph,undirected graph,previous best approximation ratio,graph g,graph h,approximation algorithm | Discrete mathematics,Approximation algorithm,Combinatorics,Vertex (geometry),Upper and lower bounds,Directed graph,Linear programming relaxation,Spanner,Feedback arc set,Mathematics,Steiner forest | Journal |
Volume | ISSN | Citations |
222, | 0890-5401 | 9 |
PageRank | References | Authors |
0.56 | 32 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Piotr Berman | 1 | 1754 | 192.48 |
| Arnab Bhattacharyya | 2 | 214 | 27.99 |
| Konstantin Makarychev | 3 | 600 | 43.65 |
| Sofya Raskhodnikova | 4 | 991 | 64.59 |
| Grigory Yaroslavtsev | 5 | 209 | 17.36 |