Parameterized Algorithms for the Drone Delivery Problem

Simon Bartlmae, Andreas Hene, Joshua Könen, Heiko Röglin · 2026

Read Parameterized Algorithms for the Drone Delivery Problem by Simon Bartlmae, Andreas Hene, Joshua Könen, Heiko Röglin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-04985.txt.

Description

Trucks and drones with different speeds and ranges must cooperate to deliver a single package across a network as fast as possible. The paper, an extended version of an ISAAC 2025 paper, comes from Simon Bartlmae and 3 co-authors. Each agent can only move inside its own area, so hand-offs must be planned.

The team settles an open question first: even on a simple path network, no efficient approximation scheme exists unless P equals NP. They then find the structure that makes the problem tractable. Overlap between agents' areas forms an intersection graph, and when that graph has small treewidth, exact algorithms run in fixed-parameter tractable time. For general networks the degree of the overlap graph also enters. When the overlap graph is a tree, a plain polynomial-time algorithm exists.

Catalog record

CREATORSimon Bartlmae, Andreas Hene, Joshua Könen, Heiko Röglin
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-04985

Browse the full library · About the Tower of Babel