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 ?


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

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

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.