5 citations · 7 across the 3 of their papers we have counts for
4 papers
Online Makespan Minimization: The Power of Restart
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang +2
We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competit…
How to Match when All Vertices Arrive Online
Zhiyi Huang, Ning Kang, Zhihao Gavin Tang +3
We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously-arrived vertices…
Online Submodular Maximization with Free Disposal: Randomization Beats 0.25 for Partition Matroids
T-H. Hubert Chan, Zhiyi Huang, Shaofeng H. -C. Jiang +2
We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm main…
Online Convex Covering and Packing Problems
T-H. Hubert Chan, Zhiyi Huang, Ning Kang
We study the online convex covering problem and online convex packing problem. The (offline) convex covering problem is modeled by the following convex program: $\min_{x \in R_+^n}…