On the hardness of approximating spanners
On the hardness of approximating spanners
复制标题
DOI：
10.1007/s00453-001-0021-y
复制
发表时间：
2001-07-01
期刊：
影响因子：
1.1
通讯作者：
Kortsarz, G
中科院分区：
文献类型：
--
作者：
Kortsarz, G
一个连通图G =（V，E）的k-图是由V的所有顶点和一个边的子集组成的子图G'，其附加性质是G'中任意两个顶点之间的距离不大于G中的距离的一个因子k。本文讨论了寻找具有多条接近最优边的空间的困难性。本文证明了对任意固定的k，逼近这类问题至少与逼近集合覆盖问题一样困难，并考虑了这类问题的加权形式，证明了k = 2和k ≥ 5时的逼近性之间的本质区别。
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 the distance in G by no more than a factor of k. This paper concerns the hardness of finding spanners with a 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, and prove an essential difference between the approximability of the case k = 2 and the case k greater than or equal to 5.