2
$\begingroup$

Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.

How to prove that this algorithm has an approximation ratio 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 every $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\colon \{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.​

$\endgroup$
1
$\begingroup$

You can find this algorithm analyzed at the very beginning of these lecture notes, or in these lecture notes (which consider a better variant of the algorithm but only analyze your variant), as well as in many other resources.

These are the first two hits when searching for makespan approximation.

$\endgroup$
4
  • $\begingroup$ where did you look? scholar.google.com has Springer.com as first! $\endgroup$ – Max N Jan 20 at 13:27
  • $\begingroup$ I used google.com. $\endgroup$ – Yuval Filmus Jan 20 at 13:30
  • $\begingroup$ sorry found the anwser, it was google Web search. $\endgroup$ – Max N Jan 20 at 13:31
  • $\begingroup$ scholar is better for Whitepapers and research work $\endgroup$ – Max N Jan 20 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.