16 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 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…
On the Approximate Core and Nucleon of Flow Games with Public Arcs
Pengfei Liu, Han Xiao, Tianhang Lu +1
We investigate flow games featuring both private arcs owned by individual players and public arcs accessible cost-free to all coalitions. We explore two solution concepts within th…
Approximate Core Allocations for Edge Cover Games
Tianhang Lu, Han Xian, Qizhi Fang
We study the approximate core for edge cover games, which are cooperative games stemming from edge cover problems. In these games, each player controls a vertex on a network $G = (…
Selectively-Amortized Resource Bounding (Extended Version)
Tianhan Lu, Bor-Yuh Evan Chang, Ashutosh Trivedi
We consider the problem of automatically proving resource bounds. That is, we study how to prove that an integer-valued resource variable is bounded by a given program expression.…
Approximate Core Allocations for Multiple Partners Matching Games
Han Xiao, Tianhang Lu, Qizhi Fang
The matching game is a cooperative game where the value of every coalition is the maximum revenue of players in the coalition can make by forming pairwise disjoint partners. The mu…
Type-directed Bounding of Collections in Reactive Programs
Tianhan Lu, Pavol Cerny, Bor-Yuh Evan Chang +1
Our aim is to statically verify that in a given reactive program, the length of collection variables does not grow beyond a given bound. We propose a scalable type-based technique…