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