In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf

Lemma 5 is given as:

The approximation factor of the modified greedy [scheduling] algorithm is 4/3.

And gives the example:

Note that 4/3 is essentially tight. Consider an instance with $m$ machines, $n = 2m+ 1$ jobs, $2m$ jobs of length $m + 1, m + 2, · · · , 2m − 1$ and one job of length $m$.

does the above example have an error as a proof of lemma 5?

I have been thinking about it over a day.


The instance in the example is "almost" the right one, however you are right that, as given, it does not prove tightness. The instance is missing two more jobs of size $m$.

After we include these two jobs, we have 2 jobs of each size from $2m-1$ to $m+1$ and 3 jobs of size $m$ (for $n=2m+1$ jobs in total, as stated).

Under the modified greedy algorithm, the maximum load will be $4m-1$. However, one can instead schedule a job of size $2m-i$ with a job of size $m+i$ for each $i=1,2,..., \lfloor m/2 \rfloor$, and the remaining 3 jobs of size $m$ separately on the same machine. The maximum load will then be $3m$.

| cite | improve this answer | |
  • $\begingroup$ I took m = 2 , then should I have jobs 2,2,2,3 ? $\endgroup$ – Manoharsinh Rana Mar 25 '19 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.