2 Search Results for "Chau, Vincent"

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.8
Parameterized Algorithms for the Drone Delivery Problem

Authors: Simon Bartlmae, Andreas Hene, Joshua Könen, and Heiko Röglin

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Timely delivery and optimal routing remain fundamental challenges in the modern logistics industry. Building on prior work that considers single-package delivery across networks using multiple types of collaborative agents with restricted movement areas (e.g., drones or trucks), we examine the complexity of the problem under structural and operational constraints. Our focus is on minimizing total delivery time by coordinating agents that differ in speed and movement range across a graph. This problem formulation aligns with the recently proposed Drone Delivery Problem with respect to delivery time (DDT), introduced by Erlebach et al. [ISAAC 2022]. We first resolve an open question posed by Erlebach et al. [ISAAC 2022] by showing that even when the delivery network is a path graph, DDT admits no polynomial-time approximation within any polynomially encodable factor a(n), unless P=NP. Additionally, we identify the intersection graph of the agents, where nodes represent agents and edges indicate an overlap of the movement areas of two agents, as an important structural concept. For path graphs, we show that DDT becomes tractable when parameterized by the treewidth w of the intersection graph, and we present an exact FPT algorithm with running time f(w)⋅poly(n,k), for some computable function f. For general graphs, we give an FPT algorithm with running time f(Δ,w)⋅poly(n,k), where Δ is the maximum degree of the intersection graph. In the special case where the intersection graph is a tree, we provide a simple polynomial-time algorithm.
Cite as

Simon Bartlmae, Andreas Hene, Joshua Könen, and Heiko Röglin. Parameterized Algorithms for the Drone Delivery Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bartlmae_et_al:LIPIcs.ISAAC.2025.8,
  author =	{Bartlmae, Simon and Hene, Andreas and K\"{o}nen, Joshua and R\"{o}glin, Heiko},
  title =	{{Parameterized Algorithms for the Drone Delivery Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.8},
  URN =		{urn:nbn:de:0030-drops-249162},
  doi =		{10.4230/LIPIcs.ISAAC.2025.8},
  annote =	{Keywords: Complexity, Delivery, FPT algorithms, Graph Theory}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.53
Throughput Maximization in the Speed-Scaling Setting

Authors: Eric Angel, Evripidis Bampis, and Vincent Chau

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We are given a set of n jobs and a single processor that can vary its speed dynamically. Each job J_j is characterized by its processing requirement (work) p_j, its release date r_j and its deadline d_j. We are also given a budget of energy E and we study the scheduling problem of maximizing the throughput (i.e. the number of jobs that are completed on time). While the preemptive energy minimization problem has been solved in polynomial time [Yao et al., FOCS'95], the complexity of the problem of maximizing the throughput remained open until now. We answer partially this question by providing a dynamic programming algorithm that solves the problem in pseudo-polynomial time. While our result shows that the problem is not strongly NP-hard, the question of whether the problem can be solved in polynomial time remains a challenging open question. Our algorithm can also be adapted for solving the weighted version of the problem where every job is associated with a weight w_j and the objective is the maximization of the sum of the weights of the jobs that are completed on time.
Cite as

Eric Angel, Evripidis Bampis, and Vincent Chau. Throughput Maximization in the Speed-Scaling Setting. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 53-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{angel_et_al:LIPIcs.STACS.2014.53,
  author =	{Angel, Eric and Bampis, Evripidis and Chau, Vincent},
  title =	{{Throughput Maximization in the Speed-Scaling Setting}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{53--62},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.53},
  URN =		{urn:nbn:de:0030-drops-44469},
  doi =		{10.4230/LIPIcs.STACS.2014.53},
  annote =	{Keywords: energy efficiency, dynamic speed scaling, offline algorithm, throughput, dynamic programming}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2014

  • Refine by Author
  • 1 Angel, Eric
  • 1 Bampis, Evripidis
  • 1 Bartlmae, Simon
  • 1 Chau, Vincent
  • 1 Hene, Andreas
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Complexity
  • 1 Delivery
  • 1 FPT algorithms
  • 1 Graph Theory
  • 1 dynamic programming
  • 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