Consider the following vorace algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime. how prove that this algorithm has a approximation ration of 2 ?
Suppose that once the algorithm is completed, processor $1$ is the busiest and assume task $l$ is the last task assigned to it. Let $s$ be the time that was used on processor $1 $ before adding task $i$. The algorithm has therefore found a valuable solution $u_1 = s + t_\ell$.
I'm stuck on how to show that :
- for everything $1 \leq j \leq k$ we have $s \leq \sum_{i: \alpha(i)=j}t_i$.
- $s \leq 1/k \; \sum_i t_i \leq u^*$ and $t_\ell \leq u^*$ and use these results to limit $u_1$ ($u^*$ is the optimal value).
Here is the definition of the Job Scheduling problem
Input: A set of $n$ tasks of length $t_1, t_2, \ldots t_n \in \mathbb N$ and $k$ processors.
A feasible solution is a function $\alpha: \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$ which assigns each task to a processor.
The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.
We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.
