Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

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 λ ∈ (0,1], we first propose a deterministic learning-augmented textscBalance algorithm that is (4/λ+1/λ2)-robust and (4+λ)-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 textscBalance benchmark~citebienkowski2013chain. 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/λ+1/λ2)-robust and (e+λ)-consistent. Finally, we conduct numerical experiments to complement our theoretical analysis and evaluate the empirical performance of our algorithms.