11 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…
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…
Flow Games with Public Arcs: the Least Core and the Nucleolus
Tianhang Lu, Han Xiao, Qizhi Fang
We study flow games with public arcs, an extension of classical cooperative flow games that allows players to use public resources. In these games, a coalition corresponds to a set…
Full characterization of core for nonlinear optimization games
Donglei Du, Qizhi Fang, Bin Liu +2
We fully characterize the core of a broad class of nonlinear games by identifying a suitable relaxation for inherent nonlinearity, directly generalizing the linear frameworks in th…