Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > $0
Suppose that you have one fast machine and one small machine, and consider jobs of the following durations: $t_1=t_2=\epsilon$, $t_3=1$, $t_4=2$.

The greedy algorithm first puts a job taking time $\epsilon$ on each machine (immaterial of tie-breaking rules). It then puts the third job on the fast machine (since it ends in $\epsilon/2$ rather than $\epsilon$), and then the fourth job on the slow machine. The makespan is $2+\epsilon$.

In contrast, if we put jobs 1,2,4 on the fast machine and job 3 on the slow machine, then the makespan is $1+\epsilon$.

This shows that your algorithm is not a $(2-\delta)$-approximation for any $\delta &gt; 0$.

Indeed, suppose, for the sake of contradiction, that the algorithm was a $(2-\delta)$-approximation for some $\delta &gt; 0$. Find $\epsilon &gt; 0$ small enough so that $(1+\epsilon)(2-\delta) &lt; 2+\epsilon$ (exercise: show that this is always possible), and consider the corresponding example.

Since the optimal makespan is at most $1+\epsilon$ and the algorithm is a $(2-\delta)$-approximation, it must produce a solution whose makespan is at most $(1+\epsilon)(2-\delta)$. However, the algorithm produces a solution with makespan $2+\epsilon &gt; (1+\epsilon)(2-\delta)$, and we reach a contradiction.



You might be able to give an even worse example. This is just to demonstrate the proof technique.

I suggest looking at the proof that the algorithm is a $k$-approximation algorithm, and try to find an example for which the analysis is tight. This will show that the algorithm is not a $(k-\delta)$-approximation for any $\delta &gt; 0$.