Minimizing Makespan in Sublinear Time via Weighted Random Sampling

Bin Fu, Yumei Huo, Hairong Zhao

We consider the classical makespan minimization scheduling problem where $n$ jobs must be scheduled on $m$ identical machines. Using weighted random sampling, we developed two subl…