From the 1 of 7 linked papers with an AI index.
7 papers
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…
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…
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…
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…
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…