# Approximation ratio of greedy algorithm for makespan

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.

now how can number of integers in the range m+1,m+2,....,2*m-1,be 2*m ?

## 1 Answer

The lecture notes might be misquoting the example. Here is a correct version, copied from lecture notes of Ola Svensson:

The 4/3 bound is tight, an infinite family of instances showing this is given below.

Instance: we are given $$m$$ machines, and $$2m+1$$ jobs. There are three jobs with processing time $$m$$, and $$2$$ jobs with processing times $$m+ 1,m+ 2,\ldots,2m−1$$ each. In case of LPT, all but one of the machines get two jobs with a total processing time of $$3m−1$$, and a single machine gets three jobs with a total of $$4m−1$$ processing time. Thus, the makespan is $$4m−1$$. OPT schedules the three $$m$$ jobs on a single machine, and the remaining jobs on the remaining $$m−1$$ machines, such that each of those machines get jobs with a total processing time of $$3m$$, thus the makespan of OPT is $$3m$$. As $$m$$ grows towards infinity the approximation ratio approaches $$4/3$$.

In the quote, LPT is the greedy algorithm. The approximation ratio for given $$m$$ is $$\frac{4m-1}{3m} = \frac43 - \frac1m$$, which tends to $$\frac 43$$ as $$m\to\infty$$.

• If m is variable,then how can number of job be fixed ie .5 ? – Manoharsinh Rana Mar 26 '19 at 4:52
• I don’t understand your question. It’s a parameter, fixed for each particular instance. – Yuval Filmus Mar 26 '19 at 5:05
• Can you explain how would you choose jobs for m=2? Because I am not getting ratio of 4/3. – Manoharsinh Rana Mar 26 '19 at 5:26
• You shouldn’t be. The approximation ratio tends to 4/3 as $m\to\infty$. – Yuval Filmus Mar 26 '19 at 5:34
• Then the number of jobs is $2((2m-1)-(m+1)+1)+3 = 2m+1$. – Yuval Filmus Mar 26 '19 at 15:27