Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs
Abstract
We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location y clears all pending requests in [0,y] at cost y. In the classical adversarial setting, we propose an e-competitive randomized algorithm against an oblivious adversary and prove a matching lower bound. Thus e is the optimal randomized competitive ratio. We then consider advice in the form of an offline feasible solution. For every confidence parameter λ∈(0,1], our deterministic learning-augmented algorithm is (1+3/λ)-robust and (1+3λ)-consistent. We also propose a randomized learning-augmented algorithm that is (e+e/λ)-robust and (e−1+λ)-consistent against an oblivious adversary. For the offline problem, we present a polynomial-time dynamic programming algorithm. Numerical experiments complement the worst-case analysis: accurate advice lowers service costs, while both learning-augmented algorithms remain stable as the advice becomes increasingly noisy.
Related
- Stochastic Augmented Lagrangian Framework with Second-Order Convergence Guarantees for Nonconvex Expectation-Constrained Optimization
- EntroPrefill: Renyi-Guided Context Pruning with Conditional Stability Guarantees for Retrieval-Augmented Generation
- Online Packet Scheduling with Deadlines and Learning
- The Fragile Coupon Collector: Random Deadlines, Critical Fragility, and Optimal Sampling
- The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs
BibTeX
@misc{lu2026online,
title = {{Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs}},
author = {Tianhang Lu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.26259},
eprint = {2609.26259},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.26259},
}
RIS
TY - UNPB
TI - Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs
AU - Tianhang Lu
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.26259
UR - https://arxiv.org/abs/2609.26259
AB - We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location y clears all pending requests in [0,y] at cost y. In the classical adversarial setting, we propose an e-competitive randomized algorithm against an oblivious adversary and prove a matching lower bound. Thus e is the optimal randomized competitive ratio. We then consider advice in the form of an offline feasible solution. For every confidence parameter λ∈(0,1], our deterministic learning-augmented algorithm is (1+3/λ)-robust and (1+3λ)-consistent. We also propose a randomized learning-augmented algorithm that is (e+e/λ)-robust and (e−1+λ)-consistent against an oblivious adversary. For the offline problem, we present a polynomial-time dynamic programming algorithm. Numerical experiments complement the worst-case analysis: accurate advice lowers service costs, while both learning-augmented algorithms remain stable as the advice becomes increasingly noisy.
ER -