Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

Abstract

This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the algorithms in terms of robustness and consistency. For each $\hat{I}»\in (0,1]$, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is $(4/\hat{I}»+1/\hat{I}{»}^2)$-robust and $(4+\hat{I}»)$-consistent. We also propose a randomized algorithm for the problem in the classical adversarial model, which is $(e+1)$-competitive against an oblivious adversary, improving over the deterministic $5$-competitive \textsc{Balance} benchmark~\cite{bienkowski2013chain}. Notably, this competitive ratio is even lower than the lower bound of $4$ for deterministic online algorithms. Moreover, we establish a lower bound of $e$ on the competitive ratio of randomized online algorithms, improving the previous lower bound of $e/(e-1)$. Besides, we combine the two ideas and obtain a randomized learning-augmented algorithm that is $(e/\hat{I}»+1/\hat{I}{»}^2)$-robust and $(e+\hat{I}»)$-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.

Topics & keywords