From the 1 of 5 linked papers with an AI index.
5 papers
Online Service with Per-Batch Maximum Delay
Tianhang Lu, Runtian Ren, Shengcai Liu +1
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 off…
Online Multi-Level Aggregation with Per-Batch Maximum Delay
Tianhang Lu, Runtian Ren, Shengcai Liu +1
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…
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
Tianhang Lu, Runtian Ren, Shengcai Liu +1
The paper designs deterministic and randomized online algorithms for line aggregation with delays, incorporating learning-augmented advice and analyzing their robustness, consisten…
Learning-Augmented Algorithms for Online Vertex Cover
Tianhang Lu, Runtian Ren, Shengcai Liu
This paper studies learning-augmented online weighted vertex cover with local advice and a tradeoff parameter . We consider two graph settings: bipartite graphs and ge…
Online Multi-level Aggregation with Delays and Stochastic Arrivals
Mathieu Mari, MichaÅ PawÅowski, Runtian Ren +1
This paper presents a new research direction for online Multi-Level Aggregation (MLA) with delays. In this problem, we are given an edge-weighted rooted tree , and we have to se…