Publikation: Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2013
Autor:innen
Funke, Stefan
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
HELMERT, Malte, ed.. Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA. Palo Alto, Calif.: AAAI Press, 2013, pp. 214-215. ISBN 978-1-57735-632-5
Zusammenfassung
In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) - a very powerful speedup technique originally developed for standard shortest path queries (Geisberger et al. 2008) - can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
route planning; Pareto-optimality; contraction hierarchies
Konferenz
The Sixth International Symposium on Combinatorial Search, 11. Juli 2013 - 13. Juli 2013, Leavenworth, WA, USA
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
FUNKE, Stefan, Sabine STORANDT, 2013. Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives. The Sixth International Symposium on Combinatorial Search. Leavenworth, WA, USA, 11. Juli 2013 - 13. Juli 2013. In: HELMERT, Malte, ed.. Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA. Palo Alto, Calif.: AAAI Press, 2013, pp. 214-215. ISBN 978-1-57735-632-5BibTex
@inproceedings{Funke2013Polyn-46628,
year={2013},
title={Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives},
isbn={978-1-57735-632-5},
publisher={AAAI Press},
address={Palo Alto, Calif.},
booktitle={Proceedings of the Sixth International Symposium on Combinatorial Search (SoCS-2013), 11 - 13 July 2013, Leavenworth, Washington, USA},
pages={214--215},
editor={Helmert, Malte},
author={Funke, Stefan and Storandt, Sabine}
}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/46628">
<dc:creator>Funke, Stefan</dc:creator>
<dc:language>eng</dc:language>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-08-07T08:17:23Z</dc:date>
<dc:contributor>Storandt, Sabine</dc:contributor>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:contributor>Funke, Stefan</dc:contributor>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/46628"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-08-07T08:17:23Z</dcterms:available>
<dcterms:issued>2013</dcterms:issued>
<dc:creator>Storandt, Sabine</dc:creator>
<dcterms:title>Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives</dcterms:title>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="eng">In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) - a very powerful speedup technique originally developed for standard shortest path queries (Geisberger et al. 2008) - can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case.</dcterms:abstract>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
