Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

Line Aggregation with Delays (LAD) is a fundamental problem in online decision-making where an algorithm must balance the cost of serving requests (which increases with distance) against the cost of delaying service (which accumulates over time). While deterministic algorithms like the classical Balance algorithm provide worst-case guarantees, they are often overly conservative. This paper investigates whether incorporating machine learning predictions (advice) or randomization can improve performance without sacrificing robustness.

The authors develop two primary algorithmic improvements for LAD. First, they propose a learning-augmented deterministic algorithm that adjusts the urgency of requests based on provided advice. By introducing a trust parameter λ, the algorithm balances the weight given to the advice versus the actual accumulated delay. Second, they introduce a randomized algorithm that replaces the fixed grid structure of the classical Balance algorithm with a randomly shifted grid. This approach effectively smooths out the worst-case scenarios inherent in deterministic grid-based strategies.

The study provides several key theoretical results:

• Deterministic Learning-Augmented Algorithm: The proposed algorithm is (4/λ + 1/λ²)-robust and (4 + λ)-consistent, allowing for a tunable trade-off between worst-case protection and performance when predictions are accurate.
• Randomized Algorithm: The new randomized algorithm achieves an (e + 1)-competitive ratio, which outperforms the best-known deterministic lower bound of 4.
• Lower Bound: The authors establish a new lower bound of e for randomized algorithms, proving that the competitive ratio cannot be improved beyond this constant.
• Combined Approach: By integrating both techniques, they derive a randomized learning-augmented algorithm that is (e/λ + 1/λ²)-robust and (e + λ)-consistent.

Numerical experiments confirm that these algorithms outperform existing methods and maintain stability even as the quality of the advice fluctuates.