# JS Approximation

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