2 Search Results for "Doering, Michael"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.10
Parameterized Complexity of Vehicle Routing

Authors: Michelle Döring, Jan Fehse, Tobias Friedrich, Paula Marten, Niklas Mohrin, Kirill Simonov, Farehe Soheil, Jakob Timm, and Shaily Verma

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The Vehicle Routing Problem (VRP) is a popular generalization of the Traveling Salesperson Problem. Instead of one salesperson traversing the entire weighted, undirected graph G, there are k vehicles available to jointly cover the set of clients C ⊆ V(G). Every vehicle must start at one of the depot vertices D ⊆ V(G) and return to its start. Capacitated Vehicle Routing (CVRP) additionally restricts the route of each vehicle by limiting the number of clients it can cover, the distance it can travel, or both. In this work, we study the complexity of VRP and the three variants of CVRP for several parameterizations, in particular focusing on the treewidth of G. We present an FPT algorithm for VRP parameterized by treewidth. For CVRP, we prove paraNP- and W[⋅]-hardness for various parameterizations, including treewidth, thereby rendering the existence of FPT algorithms unlikely. In turn, we provide an XP algorithm for CVRP when parameterized by both treewidth and the vehicle capacity.
Cite as

Michelle Döring, Jan Fehse, Tobias Friedrich, Paula Marten, Niklas Mohrin, Kirill Simonov, Farehe Soheil, Jakob Timm, and Shaily Verma. Parameterized Complexity of Vehicle Routing. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doring_et_al:LIPIcs.IPEC.2025.10,
  author =	{D\"{o}ring, Michelle and Fehse, Jan and Friedrich, Tobias and Marten, Paula and Mohrin, Niklas and Simonov, Kirill and Soheil, Farehe and Timm, Jakob and Verma, Shaily},
  title =	{{Parameterized Complexity of Vehicle Routing}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.10},
  URN =		{urn:nbn:de:0030-drops-251424},
  doi =		{10.4230/LIPIcs.IPEC.2025.10},
  annote =	{Keywords: Vehicle Routing Problem, Treewidth, Parameterized Complexity}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GIScience.2023.65
From Change Detection to Change Analytics: Decomposing Multi-Temporal Pixel Evolution Vectors (Short Paper)

Authors: Victoria Scherelis, Patrick Laube, and Michael Doering

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Change detection is a well-established process of detaining spatial and temporal changes of entities between two or more timesteps. Current advancements in digital map processing offer vast new sources of multitemporal geodata. As the temporal aspect gains complexity, the dismantling of detected changes on a pixel-based scale becomes a costly undertaking. In efforts to establish and preserve the evolution of detected changes in long time series, this paper presents a method that allows the decomposition of pixel evolution vectors into three dimensions of change, described as directed change, change variability, and change magnitude. The three dimensions of change compile to complex change analytics per individual pixels and offer a multi-faceted analysis of landscape changes on an ordinal scale. Finally, the integration of class confidence from learned uncertainty estimates illustrates the avenue to include uncertainty into the here presented change analytics, and the three dimensions of change are visualized in complex change maps.
Cite as

Victoria Scherelis, Patrick Laube, and Michael Doering. From Change Detection to Change Analytics: Decomposing Multi-Temporal Pixel Evolution Vectors (Short Paper). In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{scherelis_et_al:LIPIcs.GIScience.2023.65,
  author =	{Scherelis, Victoria and Laube, Patrick and Doering, Michael},
  title =	{{From Change Detection to Change Analytics: Decomposing Multi-Temporal Pixel Evolution Vectors}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{65:1--65:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.65},
  URN =		{urn:nbn:de:0030-drops-189604},
  doi =		{10.4230/LIPIcs.GIScience.2023.65},
  annote =	{Keywords: Digital map processing, spatio-temporal modelling, land-use change}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023

  • Refine by Author
  • 1 Doering, Michael
  • 1 Döring, Michelle
  • 1 Fehse, Jan
  • 1 Friedrich, Tobias
  • 1 Laube, Patrick
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Information systems → Spatial-temporal systems
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 Digital map processing
  • 1 Parameterized Complexity
  • 1 Treewidth
  • 1 Vehicle Routing Problem
  • 1 land-use change
  • 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