2006 | OriginalPaper | Chapter
Spanners with Slack
Authors : T. -H. Hubert Chan, Michael Dinitz, Anupam Gupta
Published in: Algorithms – ESA 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a metric (
V
,
d
), a
spanner
is a sparse graph whose shortest-path metric approximates the distance
d
to within a small multiplicative distortion. In this paper, we study the problem of
spanners with slack
: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a small constant fraction of the distances, but are then required to incur only a constant (independent of
n
) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into ℓ
p
spaces. For instance, we show that if we ignore an
ε
fraction of the distances, we can get spanners with
O
(
n
) edges and
$O(\log {\frac{1}{\epsilon}})$
distortion for the remaining distances.
We also show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. This paper complements similar results obtained in recent research on slack embeddings into normed metric spaces.