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.
Tianhan Lu, Runtian Ren, Shengcai Liu et al.· 2 citations
We study online service with one maximum-waiting-time charge per service batch. The persistent server endpoint prevents a phase-by-phase comparison with the offline optimum: an offline schedule may merge many online phases, share movement globally, and finish at unrelated endpoints. Our main contribution is a metric-independent \emph{group--trajectory certificate framework} that restores such a comparison. For ordered request groups in disjoint time windows, a certificate value is bounded both by the window length and by the metric Steiner cost of the group. After normalizing the offline schedule into consecutive arrival blocks, strictly interior groups are charged to offline delay, while boundary groups induce connectors of congestion at most two along the offline trajectory. One color class therefore has certificate sum at most $2\OPT$; a parity decomposition yields $\sum_h C_h\le4\OPT$. Consequently, any phase rule whose cost is at most $\alpha C_h$ is $4\alpha$-competitive. For visible service, this theorem yields deterministic ratios $10$ on a line, $12$ on a weighted tree, and $20$ on an arbitrary finite metric; the last algorithm is polynomial and uses a phase-local terminal-MST envelope, while an exact metric-Steiner oracle gives ratio $12$. Structurally, elective and automatic schedules can have different event structures but equal offline optimal values. The common value is computable exactly in polynomial time on lines and explicitly represented weighted trees, whereas exact optimization on arbitrary finite metrics is NP-hard. Finally, we use spatial blindness---announced requests whose locations are revealed only when visited---as a stress test: dyadic exploration preserves a constant ratio on a known finite line, while a single hidden request on a star forces a loss linear in its degree.
Tianhan Lu, Runtian Ren, Shengcai Liu et al.· 0 citations
We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an integrable fixed point; classifying all such fixed points forces the excess ratio to be at least $\sqrt{e}/2$. A truncated discrete recurrence and a Riemann-sum argument convert every strict continuous violation into a finite, algorithm-dependent but realization-oblivious input. We also exhibit a critical fixed point showing that $1+\sqrt{e}/2$ is the exact limit of this homogeneous complete-bipartite recurrence, rather than a numerical artifact.
Tianhan Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
