3 papers
cs.DS2020
Improved Lower Bound for Competitive Graph Exploration
Alexander Birx, Yann Disser, Alexander V. Hopp +1
We give an improved lower bound of 10/3 on the competitive ratio for the exploration of an undirected, edge-weighted graph with a single agent that needs to return to the starting…
math.OC2019
Improved Bounds for Open Online Dial-a-Ride on the Line
Alexander Birx, Yann Disser, Kevin Schewior
We consider the open, non-preemptive online Dial-a-Ride problem on the real line, where transportation requests appear over time and need to be served by a single server. We give a…
math.OC2019
Tight Analysis of the Smartstart Algorithm for Online Dial-a-Ride on the Line
Alexander Birx, Yann Disser
The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests appear over time and may be served in any order by a single server w…