# Job scheduling approximation

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.

## 1 Answer

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$$.

• I took m = 2 , then should I have jobs 2,2,2,3 ? – Manoharsinh Rana Mar 25 '19 at 16:57