Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies

Lade...
Vorschaubild
Dateien
Blum_2-7tivdcd91s0c9.pdf
Blum_2-7tivdcd91s0c9.pdfGröße: 482.63 KBDownloads: 190
Datum
2020
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Bookpart
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
FABRIZIO GRANDONI, , ed., GRZEGORZ HERMAN, ed., PETER SANDERS, ed.. 28th Annual European Symposium on Algorithms : ESA 2020. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f√ľr Informatik, 2020, 20. Leibniz International Proceedings in Informatics : LIPIcs. 173. eISSN 1868-8969. ISBN 978-3-95977-162-7. Available under: doi: 10.4230/LIPIcs.ESA.2020.20
Zusammenfassung

Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in ūĚí™(‚ąön) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in ūĚí™(h log D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in ő©(b_őĪ) for őĪ ‚Č• 2/3 where b_őĪ is the size of a smallest őĪ-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the ūĚí™(‚ąön) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
contraction hierarchies, search space size, balanced separator, tree decomposition
Konferenz
28th Annual European Symposium on Algorithms : ESA 2020 (Virtual Conference), 7. Sept. 2020 - 9. Sept. 2020, Pisa, Italy
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BLUM, Johannes, Sabine STORANDT, 2020. Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies. 28th Annual European Symposium on Algorithms : ESA 2020 (Virtual Conference). Pisa, Italy, 7. Sept. 2020 - 9. Sept. 2020. In: FABRIZIO GRANDONI, , ed., GRZEGORZ HERMAN, ed., PETER SANDERS, ed.. 28th Annual European Symposium on Algorithms : ESA 2020. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum f√ľr Informatik, 2020, 20. Leibniz International Proceedings in Informatics : LIPIcs. 173. eISSN 1868-8969. ISBN 978-3-95977-162-7. Available under: doi: 10.4230/LIPIcs.ESA.2020.20
BibTex
@inproceedings{Blum2020Lower-50799,
  year={2020},
  doi={10.4230/LIPIcs.ESA.2020.20},
  title={Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies},
  number={173},
  isbn={978-3-95977-162-7},
  publisher={Schloss Dagstuhl - Leibniz-Zentrum f√ľr Informatik},
  address={Dagstuhl},
  series={Leibniz International Proceedings in Informatics : LIPIcs},
  booktitle={28th Annual European Symposium on Algorithms : ESA 2020},
  editor={Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  author={Blum, Johannes and Storandt, Sabine},
  note={Article Number: 20}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/50799">
    <dcterms:issued>2020</dcterms:issued>
    <dcterms:title>Lower Bounds and Approximation Algorithms for Search Space Sizes in Contraction Hierarchies</dcterms:title>
    <dc:creator>Blum, Johannes</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:language>eng</dc:language>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by/3.0/"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/50799/1/Blum_2-7tivdcd91s0c9.pdf"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:rights>Attribution 3.0 Unported</dc:rights>
    <dc:contributor>Blum, Johannes</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/50799/1/Blum_2-7tivdcd91s0c9.pdf"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-09-11T11:24:42Z</dc:date>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2020-09-11T11:24:42Z</dcterms:available>
    <dcterms:abstract xml:lang="eng">Contraction hierarchies (CH) is a prominent preprocessing-based technique that accelerates the computation of shortest paths in road networks by reducing the search space size of a bidirectional Dijkstra run. To explain the practical success of CH, several theoretical upper bounds for the maximum search space size were derived in previous work. For example, it was shown that in minor-closed graph families search space sizes in ūĚí™(‚ąön) can be achieved (with n denoting the number of nodes in the graph), and search space sizes in ūĚí™(h log D) in graphs of highway dimension h and diameter D. In this paper, we primarily focus on lower bounds. We prove that the average search space size in a so called weak CH is in ő©(b_őĪ) for őĪ ‚Č• 2/3 where b_őĪ is the size of a smallest őĪ-balanced node separator. This discovery allows us to describe the first approximation algorithm for the average search space size. Our new lower bound also shows that the ūĚí™(‚ąön) bound for minor-closed graph families is tight. Furthermore, we deeper investigate the relationship of CH and the highway dimension and skeleton dimension of the graph, and prove new lower bound and incomparability results. Finally, we discuss how lower bounds for strong CH can be obtained from solving a HittingSet problem defined on a set of carefully chosen subgraphs of the input network.</dcterms:abstract>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/50799"/>
  </rdf:Description>
</rdf:RDF>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Pr√ľfdatum der URL
Pr√ľfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen