# Analysis of an approximation claim

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.

• This is not homework by the way. I am doing an online MOOC just so for myself.
– Ely
Commented Jul 10, 2019 at 5:28

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.

• Yes, perfect. Thank you for de-confusing my mind. I got the approach completely wrong (I cannot believe how this could happen).
– Ely
Commented Jul 11, 2019 at 9:54
• @orlp I still don't get it. He is claiming that the approximation ratio = 1.05. For input {90,30,80}. The optimal makespan = 110. He says its 120. Ratio=120/110 = 1.09. Then how his claim is true? How is the ratio 1.05 when there is a case where the ratio =1.09? Can you please explain in detail. Commented Nov 8, 2019 at 13:05
• @MaruthiAdithya We showed (by counterexample) that the algorithm is not an $1.05$ approximation algorithm. A ratio of $1.09$ is worse than that, so it is allowed to achieve that.
– orlp
Commented Nov 8, 2019 at 16:08
• @orlp Alg(I) <= 1.05 Opt(I). This is what he is claiming right? Then how can 1.09 be smaller than 1.05. Commented Nov 9, 2019 at 2:14
• @MaruthiAdithya That was the claim and we disproved it.
– orlp
Commented Nov 9, 2019 at 10:44