Show that a $\alpha$-approximation algorithm is not a ($\alpha-x$) approximation algorithm for $x > 0ドル

Question

Suppose you have a system that consists of $m$ slow machines and $k$ fast machines. The fast machines can perform twice as much work per unit time as the slow machines. Now you are given a set of n jobs; job $i$ takes time $t_i$ to process on a slow machine and time $\frac{1}{2} t_i$ to process on a fast machine. The goal is to minimize the makespan — the maximum, over all machines, of the total processing time of jobs assigned to that machine.

Algorithm: When each job arrives, we put it on the machine that currently ends the soonest(machine with smallest current load before the job is assigned). (Note that this determination involves taking into account the speeds of the machines.) This is a 3-approximation algorithm.

I want to find an example for which the algorithm is not a $(3 - x)$-approximation algorithm for any $x > 0$.

Condering that the makespan of the resulting algorithm is $T$, to do that I thought that, since the algorithm is a $(3-x)$-approximation if $T \leq (3-x)OPT$, I would just have to find an example for which $T > (3-x)OPT$. But I cannot seem to be able to find one, all the examples I find yield $T \leq (3-x)OPT$.

---

I just found a very basic example, where I have 4 jobs and 2 machines, one fast and one slow. The jobs: 4, 4, 1, 2

The algorithm would first assign job 1 to the fast machine, then job 2 to the second machine, then jobs 3 and 4 to the fast machine. This yields a makespan $T$ of 4ドル$.

The optimal makespan $OPT$ would be assigning jobs 1, 2 and 3 to the fast machine and job 4 to the slow machine, so $OPT = \frac{9}{4}$.

But then 4ドル < 9 (4\frac{9}{4})$

What am I doing wrong?

Answer 1

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 > 0$.

Indeed, suppose, for the sake of contradiction, that the algorithm was a $(2-\delta)$-approximation for some $\delta > 0$. Find $\epsilon > 0$ small enough so that $(1+\epsilon)(2-\delta) < 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 > (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 > 0$.

• nima3: How does that show that the algorithm is not a (2- x)-approximation ??
• Yuval Filmus: That's something you will have to figure out on your own. Try using the definition.
• Yuval Filmus: No. You will have to make this step on your own. You won't learn anything if we spoon-feed you. Don't be lazy! You can do it.
• Yuval Filmus: Ok, I spelled it out. I imagine that the source of difficulty is that you don't understand the definition of an approximation algorithm.
• nima3: This analysis is wrong since the greedy algorithm would put the fourth job on the fast machine since the fast machine after the third job is added ends at e/2 + 1/2, which is less than e (on the slow machine). And therefore the makespan would be: 3/2 + e/2 And it is true for any value of e > 0 that: (3/2 + e/2) <= (1 + e)(k-x). Therefore this cannot be used to prove the algorithm is not a (k-x)-approximation algorithm