Paper Info
Title
Improved approximation for the directed spanner problem
Abstract
We give an O(√n log n)-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 stretch k ≥ 1, a subgraph H = (V,EH) is a k-spanner of G if for every edge (u, v) ∈ E, the graph H contains a path from u to v of length at most k ċ d(u, v). The previous best approximation ratio was Õ(n2/3), due to Dinitz and Krauthgamer (STOC '11). We also present an improved algorithm for the important special case of directed 3-spanners with unit edge lengths. The approximation ratio of our algorithm is Õ(n1/3) which almost matches the lower bound shown by Dinitz and Krauthgamer for the integrality gap of a natural linear programming relaxation. The best previously known algorithms for this problem, due to Berman, Raskhodnikova and Ruan (FSTTCS '10) and Dinitz and Krauthgamer, had approximation ratio Õ(√n).
Year
DOI
Venue
2011
10.1007/978-3-642-22006-7_1
ICALP'11 Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I
Keywords
DocType
Volume
Improved approximation,n vertex,approximation ratio,original graph,improved algorithm,n log n,previous best approximation ratio,graph G,approximation algorithm,graph H,spanner problem,nonnegative edge length
Conference
abs/1012.4062
ISSN
Citations 
PageRank 
0302-9743
11
0.54
References 
Authors
32
5
Name
Order
Citations
PageRank
Piotr Berman11754192.48
Arnab Bhattacharyya221427.99
Konstantin Makarychev360043.65
Sofya Raskhodnikova499164.59
Grigory Yaroslavtsev520917.36