Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 13 min ago
PreprintarXiv licencearXiv

Online Multi-Level Aggregation with Maximum Delay

  • Tianhang Lu
  • Runtian Ren
  • Shengcai Liu
  • Ke Tang
Open at sourcePDFDOICite

Abstract

We study Multi-Level Aggregation with Maximum Delay (MLA-MD) on finite weighted rooted trees. Each service pays for a rooted subtree and for the maximum waiting time among the requests it clears. For the offline problem, we give an exact polynomial-time algorithm that computes both the optimum and an optimal service schedule. For the online problem, we give a deterministic $2$-competitive algorithm and, against an oblivious adversary, a randomized e/(e−1)-competitive algorithm. Both competitive ratios are optimal, even on rooted paths. We also extend the offline result and both online guarantees to service systems with submodular costs.

Related

  1. On the Delay-Constrained Maximum Concurrent Flow Problem
    Walid Ben-Ameur, Guillaume Beraud-Sudreau, Hervé Kerivin +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs
    Tianhang Lu
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Efficient conformal prediction intervals for time series: Online PID-Expert aggregation
    Guodong Liu, Yanfei Kang, Ren Miao +1
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. Unit-level aggregation breaks coverage in causal foundation models
    Gabe Schulman, Lucius E. J. Bynum, Yoav Wald
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  5. Whittle index approach to multi-server scheduling with convex delay costs and impatient customers
    Samuli Aalto
    arXivPreprintCC BY-NC-ND 4.0Full textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{lu2026online,
  title = {{Online Multi-Level Aggregation with Maximum Delay}},
  author = {Tianhang Lu and Runtian Ren and Shengcai Liu and Ke Tang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2608.06796},
  eprint = {2608.06796},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.06796},
}
RIS
TY  - UNPB
TI  - Online Multi-Level Aggregation with Maximum Delay
AU  - Tianhang Lu
AU  - Runtian Ren
AU  - Shengcai Liu
AU  - Ke Tang
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2608.06796
UR  - https://arxiv.org/abs/2608.06796
AB  - We study Multi-Level Aggregation with Maximum Delay (MLA-MD) on finite weighted rooted trees. Each service pays for a rooted subtree and for the maximum waiting time among the requests it clears. For the offline problem, we give an exact polynomial-time algorithm that computes both the optimum and an optimal service schedule. For the online problem, we give a deterministic $2$-competitive algorithm and, against an oblivious adversary, a randomized e/(e−1)-competitive algorithm. Both competitive ratios are optimal, even on rooted paths. We also extend the offline result and both online guarantees to service systems with submodular costs.
ER  -