9 papers
Online Covering with Maximum Delay under Subadditive Service Costs
Tianhang Lu, Runtian Ren, Shengcai Liu
We study online covering in which each instantaneous service pays its purchase cost and one maximum waiting time, with no effect on future requests. For static realizable services,…
Online Bin Packing with Per-Bin Maximum Delay
Tianhang Lu, Runtian Ren, Shengcai Liu
We study online bin packing with per-bin maximum delay: each sealed bin incurs a unit opening cost plus the longest waiting time among its items. Offline, this becomes a temporal-s…
Paging with Per-Replacement Maximum Delay
Tianhang Lu, Runtian Ren, Shengcai Liu
Classical paging serves every miss immediately. We study paging with per-replacement maximum delay, where loading a pending page costs one movement plus the age of its oldest outst…
Online Service with Per-Batch Maximum Delays
Tianhang Lu, Runtian Ren, Shengcai Liu +1
We study online service with per-batch maximum delays on a finite metric space. Requests arrive over time, and a server serves each batch by following a walk visiting its requests'…
Online Multi-Level Aggregation with Maximum Delay
Tianhang Lu, Runtian Ren, Shengcai Liu +1
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 requ…
Learning-Augmented and Randomized Algorithms for Line Aggregation with Delays
Tianhang Lu, Runtian Ren, Shengcai Liu +1
This paper studies learning-augmented and randomized online aggregation with delays on a line metric. We consider advice given as online suggested service lengths, and evaluate the…
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 gen…
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…
Modeling Online Paging in Multi-Core Systems
Mathieu Mari, Anish Mukherjee, Runtian Ren +1
Web requests are growing exponentially since the 90s due to the rapid development of the Internet. This process was further accelerated by the introduction of cloud services. It ha…