3 Search Results for "Laue, Sören"

Document
DOI: 10.4230/OASIcs.ATMOS.2025.13
Multi-Criteria Route Planning with Little Regret

Authors: Carina Truschel and Sabine Storandt

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
Multi-criteria route planning arises naturally in real-world navigation scenarios where users care about more than just one objective - such as minimizing travel time while also avoiding steep inclines or unpaved surfaces or toll routes. To capture the possible trade-offs between competing criteria, many algorithms compute the set of Pareto-optimal paths, which are paths that are not dominated by others with respect to the considered cost vectors. However, the number of Pareto-optimal paths can grow exponentially with the size of the input graph. This leads to significant computational overhead and results in large output sets that overwhelm users with too many alternatives. In this work, we present a technique based on the notion of regret minimization that efficiently filters the Pareto set during or after the search to a subset of specified size. Regret minimizing algorithms identify such a representative solution subset by considering how any possible user values any subset with respect to the objectives. We prove that regret-based filtering provides us with quality guarantees for the two main query types that are considered in the context of multi-criteria route planning, namely constrained shortest path queries and personalized path queries. Furthermore, we design a novel regret minimization algorithm that works for any number of criteria, is easy to implement and produces solutions with much smaller regret value than the most commonly used baseline algorithm. We carefully describe how to incorporate our regret minimization algorithm into existing route planning techniques to drastically reduce their running times and space consumption, while still returning paths that are close-to-optimal.
Cite as

Carina Truschel and Sabine Storandt. Multi-Criteria Route Planning with Little Regret. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{truschel_et_al:OASIcs.ATMOS.2025.13,
  author =	{Truschel, Carina and Storandt, Sabine},
  title =	{{Multi-Criteria Route Planning with Little Regret}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{13:1--13:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.13},
  URN =		{urn:nbn:de:0030-drops-247698},
  doi =		{10.4230/OASIcs.ATMOS.2025.13},
  annote =	{Keywords: Pareto-optimality, Regret minimization, Contraction Hierarchies}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.18
Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees

Authors: Stefan Funke, Sören Laue, and Sabine Storandt

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
In a personalized route planning query, a user can specify how relevant different criteria as travel time, gas consumption, scenicness, etc. are for his individual definition of an optimal route. Recently developed acceleration schemes for personalized route planning, which rely on preprocessing, achieve a significant speed-up over the Dijkstra baseline for a small number of criteria. But for more than five criteria, either the preprocessing becomes too complicated or the query answering is slow. In this paper, we first present a new LP-based preprocessing technique which allows to deal with many criteria efficiently. In addition, we show how to further reduce query times for all known personalized route planning acceleration schemes by considering approximate queries. We design a data structure which allows not only to have personalized costs but also individual approximation guarantees per query, allowing to trade solution quality against query time at the user's discretion. This data structure is the first to enable a speed-up of more than 100 for ten criteria while accepting only 0.01% increased costs.
Cite as

Stefan Funke, Sören Laue, and Sabine Storandt. Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 18:1-18:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.SEA.2017.18,
  author =	{Funke, Stefan and Laue, S\"{o}ren and Storandt, Sabine},
  title =	{{Personal Routes with High-Dimensional Costs and Dynamic Approximation Guarantees}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{18:1--18:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.18},
  URN =		{urn:nbn:de:0030-drops-76255},
  doi =		{10.4230/LIPIcs.SEA.2017.18},
  annote =	{Keywords: personalized route planning, contraction hierarchies, linear program, separation oracle, approximate queries}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.16
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

Authors: Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Omega(n^2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
Cite as

Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2016.16,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, S\"{o}ren},
  title =	{{Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.16},
  URN =		{urn:nbn:de:0030-drops-63670},
  doi =		{10.4230/LIPIcs.ESA.2016.16},
  annote =	{Keywords: hyperbolic random graphs, embedding, power-law graphs, hyperbolic plane}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2017
  • 1 2016

  • Refine by Author
  • 2 Laue, Sören
  • 2 Storandt, Sabine
  • 1 Bläsius, Thomas
  • 1 Friedrich, Tobias
  • 1 Funke, Stefan
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Contraction Hierarchies
  • 1 Pareto-optimality
  • 1 Regret minimization
  • 1 approximate queries
  • 1 contraction hierarchies
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact