We consider a variant of the load balancing problem, which we will refer to as $\backslash$LBHD $($for $\{\backslash$sc Load$-$Balancing$-$With$-$Half$-$The$-$Machines$-$Having$-$Double$-$Speed$\}).$ The input consists of $n$ jobs with non$-$negative processing times $t$\_1,$t$\_2,\backslash$ldots$,$ t$\_$n$$,$ and there are $$2$m$ machines, out of which $m$ are single$-$speed machines and $m$ are double$-$speed machines. Processing a job $j$ on a single$-$speed machine takes $t$\_$j$ time units, and processing it on a double$-$speed machine takes $t$\_$j$/2$$ time units. As in the regular load balancing problem, the goal is to assign the jobs to the machines so as to minimize the makespan $--$ that is$,$ the maximum, over all machines, of the time the machine needs to process the jobs assigned to it$.$ Consider the following simple algorithm for the $\backslash$LBHD problem: the algorithm considers the job in arbitrary order, and puts the next job on the double$-$speed machine with smallest load so far. In other words, the algorithm ignores the single$-$speed machines and runs the Greedy$-$Balance algorithm from lecture$/$Section $11\mathrm{.}1$ to assign the jobs to the double$-$speed machines. $\backslash$begin$\{$subproblem$\}$ Show that the approximation ratio of $$\backslash$frac$52$$ is $\{\backslash$it tight$\}$; that is show that for any $$\backslash$varepsilon$>0$$$,$ there exists an input for which the algorithm's makespan is at least $$(\backslash$frac$52-\backslash$varepsilon$)$$ as large as the optimal makespan. $\backslash$end$\{$subproblem$\}$ I was told that this excerpt from the textbook is helpful: It is not hard to give an example in which the solution is indeed close to a factor of $2$ away from optimal. Suppose we have m machines and n $=$m$($m$1)+1$jobs. The first m$($m$1)=$n $1$jobs each require time tj $=1.$ The last job is much larger; it requires time tn $=$m$.$ What does our greedy algorithm do with this sequence of jobs? It evenly balances the first n $1$ jobs, and then has to add the giant job n to one of them; the resulting makespan is T $=2$m$1.$ What does the optimal solution look like in this example? It assigns the large job to one of the machines, say, M$1,$ and evenly spreads the remaining jobs over the other m$1$ machines. This results in a makespan of m$.$ Thus the ratio between the greedy algorithm$$s solution and the optimal solution is $(2$m$1)/$m$=21/$m$,$ which is close to a factor of $2$ when m is large. See Figure $11\mathrm{.}3$ for a picture of this with m $=4$; one has to admire the perversity of the construction, which misleads the greedy algorithm into perfectly balancing everything, only to mess everything up with the final giant item. In fact, with a little care, one can improve the analysis in $(11\mathrm{.}3)$ to show that the greedy algorithm with m machines is within exactly this factor of $21/$m on every instance; the example above is really as bad as possible.

This is how I am suggested to answer the question: There's no easy way to find one LBHD input that leads to exactly a $5/2-$approximation. What the problem is asking you to find is: for every positive $>0,$ can you find an LBHD input such that running the simple algorithm results in a makespan that is at least $5/2$ times the optimal makespan on the same input? So you are tasked to find a family of inputs which can approach a $5/2-$approximation, even though it doesn't obtain it exactly. First, you prove that the algorithm's makespan is never worse $($higher$)$ than $5/2$ times the optimal makespan. Then, you prove that you cannot prove anything better than $5/2$; that is$,$ there are examples for which the algorithm's makespan is as bad $($high$)$ as $5/2-$epsilon times the optimal makespan.