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