Randomized Algorithms (Spring 2010)/Randomized approximation algorithms
Approximation Algorithms
Coping with the NP-hardness
Combinatorial approximation algorithms
Scheduling
Scheduling is a class of problems. We consider a central problem in scheduling theory: the minimum makespan scheduling.
Problem (Minimum makespan scheduling)
|
This problem is known to be NP-hard. We consider a very simple and natural algorithm:
- Schedule the jobs one by one, in an arbitrary order, each job being assigned to a machine with least amount of work so far.
This algorithms is due to Graham (1966), who also shows that the algorithm approximates the optimal makespan within a factor of 2.
Let OPT be the optimal makespan. We have two observations:
- [math]\displaystyle{ \mathrm{OPT}\ge\frac{1}{m}\sum_{j=1}^n p_j }[/math], i.e. the optimal makespan is no smaller than the average processing time.
- [math]\displaystyle{ \mathrm{OPT}\ge \max_{1\le j\le n}p_j }[/math], i.e. the optimal makespan is no smaller than the largest processing time.
Proof of the approximation factor: We assume that the last job scheduled is [math]\displaystyle{ p_n }[/math], assigned to machine [math]\displaystyle{ i }[/math], and the makespan produced by the algorithm is [math]\displaystyle{ M }[/math]. Since the algorithm assigns a job to the least loaded machine, right before [math]\displaystyle{ p_n }[/math] is scheduled, machine [math]\displaystyle{ i }[/math] whose current load is [math]\displaystyle{ M-p_n }[/math], must be the least loaded. Thus, [math]\displaystyle{ M-p_n }[/math] is no greater than the average processing time. Then,
- [math]\displaystyle{ M-p_n\le \frac{1}{m}\sum_{j=1}^n p_j\le \mathrm{OPT} }[/math].
And since [math]\displaystyle{ p_n\le\max_{1\le j\le n}p_j\le \mathrm{OPT} }[/math], it holds that [math]\displaystyle{ M=M-p_n+p_n\le 2\cdot\mathrm{OPT} }[/math].
[math]\displaystyle{ \square }[/math]
There are poly-time algorithm using different ideas with much better approximation ratio for this problem.
Knapsack
Problem (Knapsack)
|