{"id":"arxiv/2608.06796","url":"https://arxiv.org/abs/2608.06796","tags":["cs.DS","cs.DM","math.OC"],"score":0,"title":"Online Multi-Level Aggregation with Per-Batch Maximum Delay","domain":"cs.DS","source":"arxiv","authors":["Tianhang Lu","Runtian Ren","Shengcai Liu","Ke Tang"],"reviews":0,"subject":"cs.DS","summary":"We study online multi-level aggregation on finite rooted trees with a per-batch maximum-delay objective. A service pays for a rooted subtree and for the maximum waiting time among the requests cleared by that service. We show that the offline optimum admits a consecutive-arrival-block normal form and can be computed by a polynomial-time dynamic program. The same dynamic program defines the deadlines of a family of online algorithms, which we call DP-Envelope. Its deterministic endpoint is $2$-competitive. Sampling one global parameter with density $e^θ/(e-1)$ leads to an…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-07","reactions":{}}