Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

תקציר מקורי באנגליתarXiv:2607.27807v1 Announce Type: new 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 $\lambda \in (0,1]$, we first propose a deterministic learning-augmented \textsc{Balance} algorithm that is $(4/\lambda+1/\lambda^2)$-robust and $(4+\lambda)$-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 determ