Analysis of an approximation claim

Question

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 ?

Answer 1

You case (i) analysis is wrong, consider the input $60 + 60 + 60 + 20 = 200$. The most even split you can do is $60 + 60$ and $60 + 20$ which has a makespan of $120$, thus there is at least one feasible input for which professor Smart's algorithm returns the optimal result.

For case (ii) we know each job size is at most 10. Professor Smart's algorithm returns a makespan of $120$, which means one machine has a sum of jobs of $120$ and thus the other $200 - 120 = 80$.

But since we know each job has at most a size of $10$ we could move jobs over from the bigger instance to the smaller instance at least until the bigger instance hits $110$ and the smaller $90$ while being guaranteed that each job moved reduces the makespan. But $110 \cdot 1.05 < 120$ thus the algorithm is not a $1.05$ approximation algorithm.