We investigate online multi‑level aggregation on finite rooted trees under a per‑batch maximum‑delay objective. A service incurs a cost for a rooted subtree and an additional charge equal to the maximum waiting time among the requests it clears. We show that the offline optimum can be expressed in a consecutive‑arrival‑block normal form and can be computed by a polynomial‑time dynamic program. This dynamic program also defines the deadlines for a family of online algorithms, which we call DP‑Envelope. Its deterministic version achieves a competitive ratio of $2$, while sampling a global parameter with density $\frac{e^{\theta}}{e-1}$ yields a randomized algorithm with competitive ratio $\frac{e}{e-1}$ against an oblivious adversary. The deterministic guarantee matches the known fixed‑node lower bound, and we prove a matching randomized lower bound, making both guarantees optimal on every non‑degenerate rooted tree. We first develop the line metric as a warm‑up, where the algorithm and its nested block partitions admit a direct geometric interpretation. Finally, we extend the upper bounds to any realizable static service system whose normalized, non‑decreasing, submodular joint service cost satisfies the required properties.
Review: The paper fully characterizes the optimal competitive ratios for online multi‑level aggregation and provides implementable algorithmic frameworks, offering valuable guidance for future research.