5 citations · 7 across the 3 of their papers we have counts for
Showing 2018Show all
2 papers · 1 filter
cs.DS2018
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…
cs.DS2018★ 2 cited
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…