The hardness of approximating spanner problems
The hardness of approximating spanner problems
复制标题
DOI：
10.1007/s00224-006-1266-2
复制
发表时间：
2007-11-01
影响因子：
0.5
通讯作者：
Peleg, David
中科院分区：
文献类型：
--
作者：
Elkin, Michael;Peleg, David
本文探讨了一些变种的稀疏k-ε问题，并提出了硬度的结果，其近似性。以前，已知大多数k-n问题是弱不可近似的（即，对于每个k >= 2，它们是NP-难以近似的比率O（log n）），并且对于常数拉伸要求k >= 5的单位长度k-n问题是强不可近似的（即，它是NP-难以近似的比率O（2log（1-n）[27]。本文的结果大大扩展了k-ε问题的硬度范围。一般来说，对于许多k-ε问题，对于取决于手头的特定变体的拉伸要求k的某些范围，显示出强硬度。所研究的问题不同的类型的边的权重和长度，它们包括定向，增强和客户端-服务器的变体。本文还考虑了其中拉伸要求k被放松的k-极值问题（例如，k = Ω（log n））。在这些情况下，没有已知的不可逼近性结果（即使是常数近似比）的任何非线性问题。此外，已知某些版本的k-square问题具有比率退化特性;即，它们的复杂性随着拉伸要求的倒数呈指数下降。到目前为止，还没有硬结果存在排除任何k-n问题享受这一性质。本文建立了放松拉伸要求（直到k = 0（n（1-delta）），对于任何0 < delta < 1）的情况下，对各种k-Delta问题的强不可逼近性结果。它还表明，这些问题不享有的比率退化属性。
This paper examines a number of variants of the sparse k-spanner problem and presents hardness results concerning their approximability. Previously, it was known that most k-spanner problems are weakly inapproximable (namely, they are NP-hard to approximate with ratio O(log n), for every k >= 2) and that the unit-length k-spanner problem for constant stretch requirement k >= 5 is strongly inapproximable (namely, it is NP-hard to approximate with ratio O(2log(1-epsilon n))) [27]. The results of this paper significantly expand the ranges of hardness for k-spanner problems. In general, strong hardness is shown for a number of k-spanner problems, for certain ranges of the stretch requirement k depending on the particular variant at hand. The problems studied differ by the types of edge weights and lengths used, and they include directed, augmentation and client-server variants. The paper also considers k-spanner problems in which the stretch requirement k is relaxed (e.g., k = Omega(log n)). For these cases, no inapproximability results were known (even for a constant approximation ratio) for any spanner problem. Moreover, some versions of the k-spanner problem are known to enjoy the ratio-degradation property; namely, their complexity decreases exponentially with the inverse of the stretch requirement. So far, no hardness result existed precluding any k-spanner problem from enjoying this property. This paper establishes strong inapproximability results for the case of relaxed stretch requirement (up to k = 0(n(1-delta)), for any 0 < delta < 1), for a large variety of k-spanner problems. It is also shown that these problems do not enjoy the ratio-degradation property.