Answers are grounded in this paper and cite their sources.
The Online Delay Management on a Single Train Line (ODMP) deals with the question at which station a train should wait for delayed passengers, instead of forcing them to take the next train. Waiting at a station increases the delay of all passengers that are already on board, and the goal is to minimize the total passenger delay. An online algorithm learns about the number of delayed passengers at a station only when reaching this station. We study the ODMP with an additional prediction on the future input data, which an online algorithm can utilize. Two desired qualities for online algorithms with prediction are called consistency and robustness, denoting the competitive ratio in case of best and worst prediction respectively. We present a family of algorithms, which uses a hyperparameter λ ∈ ( 0 , 1 ) measuring the “doubt” about the given prediction. This allows to achieve ( 1 + λ ) -consistency and ( 1 + 1 / λ ) -robustness. Moreover, we provide a lower bound for the trade-off between consistency and robustness for two variously detailed prediction models, showing that our algorithm achieves an asymptotically optimal trade-off for small values of λ . • Family of consistent and robust online algorithms using a hyperparameter measuring the doubt about the prediction. • Proving the thightness of consistency and robustness ratio by worst case examples. • New bound on the trade-off between consistency and robustness for online delay management.
No takes yet. Share an insight, caveat, or question.
Eichhorn et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: