Before revision:  Analysis for the regime of k}  ^{(n)} between o(n^{1/4) and \Theta(n) remains open} \le  .
After revision:  Analysis for the regime of k} ^{(n)} between o(n^{1/4) and \Theta(n) remains open} \le n. The key component of our proof is a new technique we develop, called "Poisson oversampling". Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation .