# Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays

arXiv: https://arxiv.org/abs/2607.27807 · HTML: https://mlsanity.com/paper/2607.27807/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 30 Jul 2026.

## Builds on (most cited first, 18 of 18)

- [WILDS: A Benchmark of in-the-Wild Distribution Shifts](https://mlsanity.com/paper/2012.07421/) (2020)
- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Secretary and Online Matching Problems with Machine Learned Advice](https://mlsanity.com/paper/2006.01026/) (2020)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Online Dynamic Acknowledgement with Learned Predictions](https://mlsanity.com/paper/2305.18227/) (2023)
- [Learning-Augmented Online Bidding in Stochastic Settings](https://mlsanity.com/paper/2510.25582/) (2025)
- [Better Approximation Bounds for the Joint Replenishment Problem](https://mlsanity.com/paper/1307.2531/) (2013)
- [Online Multi-level Aggregation with Delays and Stochastic Arrivals](https://mlsanity.com/paper/2404.09711/) (2024)
- [Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs](https://mlsanity.com/paper/2410.18535/) (2024)
- [Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs](https://mlsanity.com/paper/2507.16096/) (2025)
- [Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines](https://mlsanity.com/paper/2511.16094/) (2025)
- [Online TCP Acknowledgment under General Delays](https://mlsanity.com/paper/2604.13428/) (2026)
- [O(mboxdepth)-Competitive Algorithm for Online Multi-level Aggregation](https://mlsanity.com/paper/1701.01936/) (2017)
- [General Framework for Metric Optimization Problems with Delay or with Deadlines](https://mlsanity.com/paper/1904.07131/) (2019)
- [Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment](https://mlsanity.com/paper/2407.15809/) (2024)
- [Beyond Monotone Delays for Multi-Level Aggregation](https://mlsanity.com/paper/2607.04317/) (2026)

## Abstract (arXiv)

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.