TY - GEN
T1 - On the hardness of approximating spanners
AU - Kortsarz, Guy
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.
PY - 1998
Y1 - 1998
N2 - A k-spanner of a connected graph G = (V, E) is a subgraph Gʹ consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in Gʹ is larger than that distance in G by no more than a factor of k. This paper concerns the hardness of finding spanners with the number of edges close to the optimum. It is proved that for every fixed k approximating the spanner problem is at least as hard as approximating the set cover problem We also consider a weighted version of the spanner problem. We prove that in the case k = 2 the problem admits an O(log n)-ratio approximation, and in the case k ≥ 5, there is no 2log1-ϵ n-ratio approximation, for any ϵ > 0, unless NP ⊆ DTIME(npolylog n).
AB - A k-spanner of a connected graph G = (V, E) is a subgraph Gʹ consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in Gʹ is larger than that distance in G by no more than a factor of k. This paper concerns the hardness of finding spanners with the number of edges close to the optimum. It is proved that for every fixed k approximating the spanner problem is at least as hard as approximating the set cover problem We also consider a weighted version of the spanner problem. We prove that in the case k = 2 the problem admits an O(log n)-ratio approximation, and in the case k ≥ 5, there is no 2log1-ϵ n-ratio approximation, for any ϵ > 0, unless NP ⊆ DTIME(npolylog n).
UR - http://www.scopus.com/inward/record.url?scp=84958968556&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958968556&partnerID=8YFLogxK
U2 - 10.1007/BFb0053970
DO - 10.1007/BFb0053970
M3 - Conference contribution
AN - SCOPUS:84958968556
SN - 3540647368
SN - 9783540647362
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 135
EP - 146
BT - Approximation Algorithms for Combinatorial Optimization - International Workshop, APPROX 1998, Proceedings
A2 - Rolim, José
A2 - Jansen, Klaus
PB - Springer Verlag
T2 - International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 1998
Y2 - 18 July 1998 through 19 July 1998
ER -