Model Releases
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 servi
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 extsc{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 extsc{Balance} benchmark~ite{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.
Related
- Learning-Augmented Algorithms for Online Vertex Cover
- The Secretary Problem with a Stochastic Precursor
- Learning Safely Without Knowing the World:COMPASS-Hedge
- Learning-Accelerated Optimization-based Trajectory Planning for Cooperative Aerial-Ground Handover Missions
Source: arXiv cs.LG | 2026-07-31