Online Multi-Level Aggregation with Per-Batch Maximum Delay
TL;DR
The deterministic guarantee matches the known fixed-node lower bound, and the matching randomized lower bound are proved, ensuring that both guarantees are optimal on every nondegenerate rooted tree.
Abstract
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^\theta/(e-1)$ leads to an $e/(e-1)$-competitive randomized algorithm against an oblivious adversary. The deterministic guarantee matches the known fixed-node lower bound, and we prove a matching randomized lower bound. Thus, both guarantees are optimal on every nondegenerate rooted tree. We first develop the line metric as a warm-up, where the algorithm and its nested block partitions have a direct geometric interpretation. Finally, we show that the upper bounds extend to every realizable static service system with a normalized, nondecreasing, submodular joint service cost.