Search Results

Documents authored by Breitling, Johannes

Artifact
Software
DOI: 10.4230/artifacts.27678
RagnarGrootKoerkamp/quickheap

Authors: Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams

Abstract
Cite as

Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams. RagnarGrootKoerkamp/quickheap (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27678,
   title = {{RagnarGrootKoerkamp/quickheap}}, 
   author = {Breitling, Johannes and Groot Koerkamp, Ragnar and Williams, Marvin},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2cead1c11619177756143a9713ff21207d29fabd;origin=https://github.com/RagnarGrootKoerkamp/quickheap;visit=swh:1:snp:e0266e2ec33db11f26f6e3085d18ce1756621d86;anchor=swh:1:rev:44e0d1819be4eb414f91b55a5a9ebc8fc7f57e49}{\texttt{swh:1:dir:2cead1c11619177756143a9713ff21207d29fabd}} (visited on 2026-08-25)},
   url = {https://github.com/RagnarGrootKoerkamp/quickheap},
   doi = {10.4230/artifacts.27678},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.16
SimdQuickHeap: The QuickHeap Reconsidered

Authors: Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Motivation. Priority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is likely the implicit binary heap, even though it has frequent cache misses and is hard to optimize using e.g. SIMD instructions. Contributions. We introduce the SimdQuickHeap, a variant of the QuickHeap that was introduced by Navarro and Paredes in 2010. As suggested by the name, the data structure bears some similarity to QuickSort. We modify the data layout of the original QuickHeap to have all pivots adjacent in memory, with elements between consecutive pivots stored in dedicated buckets. This allows efficient SIMD implementations for both partitioning of buckets and scanning the list of pivots to find the bucket to append newly inserted elements to. The SimdQuickHeap has amortized expected complexity O(log n) per operation, which improves to O((1/W) log n) in non-degenerate cases, where W is the number of words in a SIMD register. In this case, the I/O-complexity is amortized O(1/B) per push and O((1/B) log₂(n/M)) per pop. Results. In synthetic benchmarks, the SimdQuickHeap is 1.2× to 1.7× as fast as the monotone radix heap, the next-best competitor, and 1.4× to 2.8× as fast as the superscalar sample queue, the fastest comparison-based priority queue. The SimdQuickHeap needs around 1.5log₂ n comparisons and log₂ n nanoseconds per pair of push and pop operations. On graph benchmarks with Dijkstra’s shortest path algorithm and Jarník-Prim’s minimum spanning tree algorithm, the SimdQuickHeap is consistently the fastest.
Cite as

Johannes Breitling, Ragnar Groot Koerkamp, and Marvin Williams. SimdQuickHeap: The QuickHeap Reconsidered. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 16:1-16:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:LIPIcs.ESA.2026.16,
  author =	{Breitling, Johannes and Groot Koerkamp, Ragnar and Williams, Marvin},
  title =	{{SimdQuickHeap: The QuickHeap Reconsidered}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{16:1--16:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.16},
  URN =		{urn:nbn:de:0030-drops-271527},
  doi =		{10.4230/LIPIcs.ESA.2026.16},
  annote =	{Keywords: Heap, SIMD, Priority Queue}
}
Artifact
Software
DOI: 10.4230/artifacts.24437
karri-with-transfers

Authors: Johannes Breitling and Moritz Laupichler

Abstract
Cite as

Johannes Breitling, Moritz Laupichler. karri-with-transfers (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24437,
   title = {{karri-with-transfers}}, 
   author = {Breitling, Johannes and Laupichler, Moritz},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:2e1d2d7c9139eb1a02b7cdd760c7c13365d35805;origin=https://github.com/JohannesBreitling/karri-with-transfers;visit=swh:1:snp:3b2c376750a7e258e80ce8925fb368460ff05c6d;anchor=swh:1:rev:e3f23d16c4b0afa908e0d5edf32f02af06d0c391}{\texttt{swh:1:dir:2e1d2d7c9139eb1a02b7cdd760c7c13365d35805}} (visited on 2025-10-17)},
   url = {https://github.com/JohannesBreitling/karri-with-transfers},
   doi = {10.4230/artifacts.24437},
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.15
Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques

Authors: Johannes Breitling and Moritz Laupichler

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

Abstract
We introduce a first-of-its-kind efficient, exact algorithm for the dynamic taxi-sharing problem with single-transfer journeys, i.e., a dispatcher that assigns traveler requests to a fleet of shared taxi-like vehicles allowing transfers between vehicles. We extend an existing no-transfer solution by collecting all viable pickup and dropoff vehicles for a request and computing the optimal transfer point for every pair of vehicles. We analyze underlying shortest-path problems and employ state-of-the-art routing algorithms to compute distances on-the-fly, which serves as the basis of dispatching requests with exact and up-to-date travel time information. We utilize constraints on existing routes, pruning techniques for transfer points, and both instruction- and thread-level parallelism to speed up the computation of the best assignment for every traveler. In addition to the exact variant, we propose a tunable heuristic approach that sacrifices solution quality in favor of improved running time. We evaluate our algorithm on a large road network with realistic input sets (up to 150000 requests). We demonstrate the effectiveness of our speedup techniques and the heuristic. We show first results on the benefits of transfers for taxi sharing on dense request sets, proving that our algorithm is well suited for the analysis of taxi sharing with transfers on large input instances.
Cite as

Johannes Breitling and Moritz Laupichler. Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{breitling_et_al:OASIcs.ATMOS.2025.15,
  author =	{Breitling, Johannes and Laupichler, Moritz},
  title =	{{Exact and Heuristic Dynamic Taxi Sharing with Transfers Using Shortest-Path Speedup Techniques}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{15:1--15:22},
  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.15},
  URN =		{urn:nbn:de:0030-drops-247718},
  doi =		{10.4230/OASIcs.ATMOS.2025.15},
  annote =	{Keywords: Dynamic taxi sharing, ride pooling, dial-a-ride problem, transfers, route planning}
}

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