Improved Approximation for the Directed Spanner Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

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

ABSTRACT

We give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}\log n)$\end{document}-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 stretchk ≥ 1, a subgraph H = (V,EH) 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{2/3})$\end{document}, 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{1/3})$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(\sqrt{n})$\end{document}. More... »

PAGES

1-12

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-642-22005-0
978-3-642-22006-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1

DOI

http://dx.doi.org/10.1007/978-3-642-22006-7_1

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1036034221


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Massachusetts Institute of Technology, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Massachusetts Institute of Technology, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhattacharyya", 
        "givenName": "Arnab", 
        "id": "sg:person.012357145015.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J.\u00a0Watson Research Center, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J.\u00a0Watson Research Center, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Makarychev", 
        "givenName": "Konstantin", 
        "id": "sg:person.013616666067.80", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013616666067.80"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Raskhodnikova", 
        "givenName": "Sofya", 
        "id": "sg:person.07502404747.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pennsylvania State University, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Pennsylvania State University, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yaroslavtsev", 
        "givenName": "Grigory", 
        "id": "sg:person.015277345473.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "We give an \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(\\sqrt{n}\\log n)$\\end{document}-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\u2009=\u2009(V,E) with nonnegative edge lengths d:\u00a0E\u2009\u2192\u2009\u211d\u2009\u2265\u20090 and a stretchk\u2009\u2265\u20091, a subgraph H\u2009=\u2009(V,EH) is a k-spanner of G if for every edge (u,v)\u2009\u2208\u2009E, the graph H contains a path from u to v of length at most k \u00b7d(u,v). The previous best approximation ratio was \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(n^{2/3})$\\end{document}, due to Dinitz and Krauthgamer\u00a0(STOC \u201911).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 \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(n^{1/3})$\\end{document} 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 \u201910) and Dinitz and Krauthgamer, had approximation ratio \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\tilde{O}(\\sqrt{n})$\\end{document}.", 
    "editor": [
      {
        "familyName": "Aceto", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "familyName": "Henzinger", 
        "givenName": "Monika", 
        "type": "Person"
      }, 
      {
        "familyName": "Sgall", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-22006-7_1", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-22005-0", 
        "978-3-642-22006-7"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "approximation ratio", 
      "graph G", 
      "natural linear programming relaxation", 
      "important special case", 
      "linear programming relaxation", 
      "best approximation ratio", 
      "unit edge lengths", 
      "sparse subgraphs", 
      "k-spanner", 
      "programming relaxation", 
      "original graph", 
      "sparse spanners", 
      "approximation algorithm", 
      "integrality gap", 
      "graph H", 
      "special case", 
      "n vertices", 
      "subgraph H", 
      "Krauthgamer", 
      "spanner problem", 
      "previous best approximation ratio", 
      "length d", 
      "edge length", 
      "algorithm", 
      "graph", 
      "improved algorithm", 
      "problem", 
      "Dinitz", 
      "Raskhodnikova", 
      "approximation", 
      "Ruan", 
      "vertices", 
      "spanners", 
      "subgraphs", 
      "Berman", 
      "edge", 
      "relaxation", 
      "path", 
      "distance", 
      "length", 
      "ratio", 
      "cases", 
      "gap"
    ], 
    "name": "Improved Approximation for the Directed Spanner Problem", 
    "pagination": "1-12", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036034221"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-22006-7_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-22006-7_1", 
      "https://app.dimensions.ai/details/publication/pub.1036034221"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_279.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-22006-7_1"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-22006-7_1'


 

This table displays all metadata directly associated to this object as RDF triples.

146 TRIPLES      22 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-22006-7_1 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nfc78ccb31a47480ba747e1930a79c0eb
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description We give an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{n}\log n)$\end{document}-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 stretchk ≥ 1, a subgraph H = (V,EH) 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{2/3})$\end{document}, 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(n^{1/3})$\end{document} 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\tilde{O}(\sqrt{n})$\end{document}.
7 schema:editor N44e805dfa48f49619c0fa2aafb8a54fb
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nb8ba7c87ea664ab09d5cafb5f9d0fc3a
11 schema:keywords Berman
12 Dinitz
13 Krauthgamer
14 Raskhodnikova
15 Ruan
16 algorithm
17 approximation
18 approximation algorithm
19 approximation ratio
20 best approximation ratio
21 cases
22 distance
23 edge
24 edge length
25 gap
26 graph
27 graph G
28 graph H
29 important special case
30 improved algorithm
31 integrality gap
32 k-spanner
33 length
34 length d
35 linear programming relaxation
36 n vertices
37 natural linear programming relaxation
38 original graph
39 path
40 previous best approximation ratio
41 problem
42 programming relaxation
43 ratio
44 relaxation
45 spanner problem
46 spanners
47 sparse spanners
48 sparse subgraphs
49 special case
50 subgraph H
51 subgraphs
52 unit edge lengths
53 vertices
54 schema:name Improved Approximation for the Directed Spanner Problem
55 schema:pagination 1-12
56 schema:productId N155c50e69d174a28a42ac2e4d344a7d2
57 N3e88e7b2e88b46c3acb8f473079bb419
58 schema:publisher N5b833494cdfe4fc199cdf930191c21aa
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036034221
60 https://doi.org/10.1007/978-3-642-22006-7_1
61 schema:sdDatePublished 2022-08-04T17:17
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N652342ddf6d14c0880e73d2022a8f86f
64 schema:url https://doi.org/10.1007/978-3-642-22006-7_1
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N145ce7fb128f4debac1e1237e32652d2 rdf:first sg:person.012357145015.18
69 rdf:rest Na3d906359db4401880515e5468575fd5
70 N155c50e69d174a28a42ac2e4d344a7d2 schema:name doi
71 schema:value 10.1007/978-3-642-22006-7_1
72 rdf:type schema:PropertyValue
73 N3e88e7b2e88b46c3acb8f473079bb419 schema:name dimensions_id
74 schema:value pub.1036034221
75 rdf:type schema:PropertyValue
76 N44e805dfa48f49619c0fa2aafb8a54fb rdf:first N75a0cca81bcf46979adb2ede06cde420
77 rdf:rest Ne7f3aac107424f06bcf0b6dd615cc459
78 N4d85352472504929a2f6550cba0a2bff schema:familyName Sgall
79 schema:givenName Jiří
80 rdf:type schema:Person
81 N5b833494cdfe4fc199cdf930191c21aa schema:name Springer Nature
82 rdf:type schema:Organisation
83 N652342ddf6d14c0880e73d2022a8f86f schema:name Springer Nature - SN SciGraph project
84 rdf:type schema:Organization
85 N68f5cc1ce92b440fa5a6848b4c5b52ab rdf:first sg:person.07502404747.45
86 rdf:rest Neac9077bd33d441a808b76dc281abe6d
87 N75a0cca81bcf46979adb2ede06cde420 schema:familyName Aceto
88 schema:givenName Luca
89 rdf:type schema:Person
90 Na3d906359db4401880515e5468575fd5 rdf:first sg:person.013616666067.80
91 rdf:rest N68f5cc1ce92b440fa5a6848b4c5b52ab
92 Nb8ba7c87ea664ab09d5cafb5f9d0fc3a schema:isbn 978-3-642-22005-0
93 978-3-642-22006-7
94 schema:name Automata, Languages and Programming
95 rdf:type schema:Book
96 Ndbbab76470df4e6082545733f199c976 rdf:first N4d85352472504929a2f6550cba0a2bff
97 rdf:rest rdf:nil
98 Ne2d9a510483240d486c9dfe4731831b4 schema:familyName Henzinger
99 schema:givenName Monika
100 rdf:type schema:Person
101 Ne7f3aac107424f06bcf0b6dd615cc459 rdf:first Ne2d9a510483240d486c9dfe4731831b4
102 rdf:rest Ndbbab76470df4e6082545733f199c976
103 Neac9077bd33d441a808b76dc281abe6d rdf:first sg:person.015277345473.26
104 rdf:rest rdf:nil
105 Nfc78ccb31a47480ba747e1930a79c0eb rdf:first sg:person.01274506210.27
106 rdf:rest N145ce7fb128f4debac1e1237e32652d2
107 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
108 schema:name Mathematical Sciences
109 rdf:type schema:DefinedTerm
110 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
111 schema:name Numerical and Computational Mathematics
112 rdf:type schema:DefinedTerm
113 sg:person.012357145015.18 schema:affiliation grid-institutes:grid.116068.8
114 schema:familyName Bhattacharyya
115 schema:givenName Arnab
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357145015.18
117 rdf:type schema:Person
118 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
119 schema:familyName Berman
120 schema:givenName Piotr
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
122 rdf:type schema:Person
123 sg:person.013616666067.80 schema:affiliation grid-institutes:grid.481554.9
124 schema:familyName Makarychev
125 schema:givenName Konstantin
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013616666067.80
127 rdf:type schema:Person
128 sg:person.015277345473.26 schema:affiliation grid-institutes:grid.29857.31
129 schema:familyName Yaroslavtsev
130 schema:givenName Grigory
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015277345473.26
132 rdf:type schema:Person
133 sg:person.07502404747.45 schema:affiliation grid-institutes:grid.29857.31
134 schema:familyName Raskhodnikova
135 schema:givenName Sofya
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07502404747.45
137 rdf:type schema:Person
138 grid-institutes:grid.116068.8 schema:alternateName Massachusetts Institute of Technology, USA
139 schema:name Massachusetts Institute of Technology, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.29857.31 schema:alternateName Pennsylvania State University, USA
142 schema:name Pennsylvania State University, USA
143 rdf:type schema:Organization
144 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, USA
145 schema:name IBM T.J. Watson Research Center, USA
146 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...