Spanners with slack

T. H.Hubert Chan, Michael Dinitz, Anupam Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 e fraction of the distances, we can get spanners with O(n) edges and O(log 1/ε) 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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2006 - 14th Annual European Symposium, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)3540388753, 9783540388753
StatePublished - 2006
Event14th Annual European Symposium on Algorithms, ESA 2006 - Zurich, Switzerland
Duration: Sep 11 2006Sep 13 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4168 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other14th Annual European Symposium on Algorithms, ESA 2006

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Spanners with slack'. Together they form a unique fingerprint.

Cite this