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 ?

  • $\begingroup$ Can you tell us why you posted this question which has almost the same body as the another question you posted just 5 hours before, which seems having a nice answer? $\endgroup$ – Apass.Jack Mar 27 at 2:00

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 at 4:52
  • $\begingroup$ I don’t understand your question. It’s a parameter, fixed for each particular instance. $\endgroup$ – Yuval Filmus Mar 26 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 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 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 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.