7 papers · 1 filter
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 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…
Online Line Aggregation with Deadlines: Randomized Guarantees and Learning-Augmented Tradeoffs
Tianhang Lu
We study online line aggregation with deadlines, where requests arrive over time on the positive half-line and a service at location clears all pending requests in at c…
A New Lower Bound for Online Vertex Cover under Vertex Arrivals
Tianhang Lu
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…