Randomized Algorithms (Spring 2010)/Randomized approximation algorithms: Difference between revisions
imported>WikiSysop |
imported>WikiSysop No edit summary |
||
Line 7: | Line 7: | ||
==== Scheduling ==== | ==== Scheduling ==== | ||
Scheduling is a class of problems. We consider a central problem in scheduling theory: the '''minimum makespan scheduling'''. | Scheduling is a class of problems. We consider a central problem in scheduling theory: the '''minimum makespan scheduling'''. | ||
{|border="1" | |||
|'''Problem (Minimum makespan scheduling)''' | |||
:Given processing times for <math>n</math> jobs, <math>p_1,p_2,\ldots,p_n</math>, and an integer <math>m</math>, find an assignment of the jobs to <math>m</math> identical machines so that the completion time, also called the '''makespan''', is minimum. | |||
:Formally, given as input a sequence <math>p_1,p_2,\ldots,p_n</math> and an integer <math>m</math>, find an <math>h:[n]\rightarrow[m]</math> such that <math>\max_{i\in[m]}\sum_{j\in h^{-1}(i)}p_j</math> is minimized. | |||
|} | |||
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>\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>\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>p_n</math>, assigned to machine <math>i</math>, and the makespan produced by the algorithm is <math>M</math>. Since the algorithm assigns a job to the least loaded machine, right before <math>p_n</math> is scheduled, machine <math>i</math> whose current load is <math>M-p_n</math>, must be the least loaded. Thus, <math>M-p_n</math> is no greater than the average processing time. Then, | |||
:<math>M-p_n\le \frac{1}{m}\sum_{j=1}^n p_j\le \mathrm{OPT}</math>. | |||
And since <math>p_n\le\max_{1\le j\le n}p_j\le \mathrm{OPT}</math>, it holds that <math>M=M-p_n+p_n\le 2\cdot\mathrm{OPT}</math>. | |||
<math>\square</math> | |||
There are poly-time algorithm using different ideas with much better approximation ratio for this problem. | |||
==== Knapsack ==== | ==== Knapsack ==== | ||
{|border="1" | |||
|'''Problem (Knapsack)''' | |||
:Given a set <math>S=\{a_1,a_2,\ldots,a_n\}</math>of objects, each with specified size <math>w_i\in\mathbb{Z}^+</math> and profit <math>p_i\mathbb{Z}^+</math>, and a knapsack capacity <math>B</math>, find a subset of objects whose total size is bounded by <math>B</math> and total profits is maximized. | |||
|} | |||
=== LP-based approximation algorithms === | === LP-based approximation algorithms === |
Revision as of 09:09, 27 May 2010
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)
|