Search papers, labs, and topics across Lattice.
This paper investigates learning-augmented and randomized online aggregation with delays on a line metric, introducing a deterministic \textsc{Balance} algorithm that achieves $(4/\lambda+1/\lambda^2)$-robustness and $(4+\lambda)$-consistency. It also presents a randomized algorithm that outperforms the deterministic benchmark by achieving an $(e+1)$-competitive ratio against an oblivious adversary, which is below the deterministic lower bound of 4. Additionally, the authors derive a new lower bound of $e$ for randomized online algorithms and propose a combined approach yielding a randomized learning-augmented algorithm with improved robustness and consistency metrics.
Randomized algorithms can outperform deterministic benchmarks in online aggregation, achieving competitive ratios below established lower bounds.
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 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/\lambda+1/\lambda^2)$-robust and $(e+\lambda)$-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.
