Consider the load balancing problem on two machines. Thus we want to distribute a set of $n$ jobs with processing times $t_1,...,t_n$ over two machines such that the makespan (maximum of the processing times of the two machines) is minimized. Professor Smart has designed an approximation algorithm Alg for this problem, and he claims that his algorithm is a $1.05$ approximation algorithm. We run Alg on a problem instance where the total size of all jobs is $200$, and Alg returns a solution whose makespan is $120$.
(i) Suppose that we know that all job sizes are at most $100$. Can we then conclude that professor Smart's claim is false?
(ii) Same question when all job sizes are at most $10$.
Let's talk about the case (i):
We know that $\sum{t_i} = 200$ and that $t_i \leq 100$. The makespan of the Algorithm $Alg = 120$, so $Alg \leq 1.05 * OPT$. We have no other information about the algorithm used. A lower bound would be $LB = max( \frac{\sum{t_i}}{2}, max(t_i)) = max (100,100) = 100$ so I would say for that particular instance we'd have $120 \leq 1.05 * 100 = 105$ which means the claim would be false.
Likewise for the case (ii).
My answer is marked as incorrect, and I am struggling to do the right analysis.
Can anyone help please ?