Minimizing Makespan in Sublinear Time via Weighted Random Sampling

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 sublinear time approximation schemes: one for the case where $n$ is known and the other for the case where $n$ is unknown. Both algorithms not only give a $(1+3\epsilon )$-approximation to the optimal makespan but also generate a sketch schedule. Our first algorithm, which targets the case where $n$ is known and draws samples in a single round under weighted random sampling, has a running time of $\tilde{O}(\frac{m^5}{{\epsilon }^4}\sqrt{n}+A(\text{ceiling}\frac{m}{\epsilon },\epsilon ))$, where $A(\mathcal{N},\alpha )$ is the time complexity of any $(1+\alpha )$-approximation scheme for the makespan minimization of $\mathcal{N}$ jobs. The second algorithm addresses the case where $n$ is unknown. It uses adaptive weighted random sampling, %$\mathit{\text{that}}\mathit{\text{is}}$, it draws samples in several rounds, adjusting the number of samples after each round, and runs in sublinear time $\tilde{O}(\frac{m^5}{{\epsilon }^4}\sqrt{n}+A(\text{ceiling}\frac{m}{\epsilon },\epsilon ))$. We also provide an implementation that generates a weighted random sample using $O(\log n)$ uniform random samples.