Improved approximation for the directed spanner problem

Piotr Berman*, Arnab Bhattacharyya, Konstantin Makarychev, Sofya Raskhodnikova, Grigory Yaroslavtsev

*Corresponding author for this work

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

16 Scopus citations

Abstract

We give an -approximation algorithm for the problem of finding the sparsest spanner of a given directed graph G on n vertices. A spanner of a graph is a sparse subgraph that approximately preserves distances in the original graph. More precisely, given a graph G∈=∈(V,E) with nonnegative edge lengths d: E → ℝ≥0 and a stretch k ≥ 1, a subgraph H = (V,E H ) is a k-spanner of G if for every edge (u,v)ε E, the graph H contains a path from u to v of length at most k •d(u,v). The previous best approximation ratio was , due to Dinitz and Krauthgamer (STOC '11). We also present an improved algorithm for the important special case of directed 3-spanners with unit edge lengths. The approximation ratio of our algorithm is which almost matches the lower bound shown by Dinitz and Krauthgamer for the integrality gap of a natural linear programming relaxation. The best previously known algorithms for this problem, due to Berman, Raskhodnikova and Ruan (FSTTCS '10) and Dinitz and Krauthgamer, had approximation ratio .

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings
Pages1-12
Number of pages12
EditionPART 1
DOIs
StatePublished - Jul 11 2011
Event38th International Colloquium on Automata, Languages and Programming, ICALP 2011 - Zurich, Switzerland
Duration: Jul 4 2011Jul 8 2011

Publication series

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

Other

Other38th International Colloquium on Automata, Languages and Programming, ICALP 2011
CountrySwitzerland
CityZurich
Period7/4/117/8/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved approximation for the directed spanner problem'. Together they form a unique fingerprint.

  • Cite this

    Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S., & Yaroslavtsev, G. (2011). Improved approximation for the directed spanner problem. In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings (PART 1 ed., pp. 1-12). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6755 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-22006-7_1