《算法设计与分析-近似算法》由会员分享，可在线阅读，更多相关《算法设计与分析-近似算法（14页珍藏版）》请在金锄头文库上搜索。
1、11Chapter 11Approximation Algorithms2Approximation AlgorithmsQ. Suppose I need to solve an NP-hard problem. What should I do? A. Theory says youre unlikely to find a poly-time algorithm.Must sacrifice one of three desired features.?Solve problem to optimality.?Solve problem in poly-time.?Solve arbit
2、rary instances of the problem.-approximation algorithm.?Guaranteed to run in poly-time.?Guaranteed to solve arbitrary instance of the problem?Guaranteed to find solution within ratio of true optimum.Challenge. Need to prove a solutions value is close to optimum, without even knowing what optimum val
3、ue is!11.1 Load Balancing24Load BalancingInput. m identical machines; n jobs, job j has processing time tj.?Job j must run contiguously on one machine.?A machine can process at most one job at a time.Def. Let J(i) be the subset of jobs assigned to machine i. The load of machine i is Li= j J(i)tj. De
4、f. The makespan is the maximum load on any machine L = maxiLi.Load balancing. Assign each job to a machine to minimize makespan.Decision Version. Is the makespan bound by a number K? 5Machine 2Machine 1adfbcegyesLoad Balancing on 2 MachinesClaim. Load balancing is hard even if only 2 machines. Pf. N
5、UMBER-PARTITIONINGPLOAD-BALANCE.adfbcgelength of job fTimeL0machine 1machine 2NP-complete 6Greedy-scheduling algorithm.?Consider n jobs in some fixed order.?Assign job j to machine whose load is smallest so far.Implementation. O(n log m) using a priority queue.Load Balancing: Greedy SchedulingGreedy
6、-Scheduling(m, n, t1,t2,tn) for i = 1 to m Li 0 J(i) for j = 1 to n i = argmink Lk J(i) J(i) j Li Li + tj return J(1), , J(m) jobs assigned to machine iload on machine imachine i has smallest loadassign job j to machine iupdate load of machine i37-approximationAn algorithm for an optimization proble
7、m is a -approximation if the solution found by the algorithm is always within a factor of the optimal solution. Minimization Problem: = approximate-solution/optimal-solutionMaximization Problem: = optimal-solution/approximate-solution8Load Balancing: Greedy Scheduling AnalysisTheorem. Graham, 1966 G
8、reedy algorithm is a 2-approximation.?First worst-case analysis of an approximation algorithm.?Need to compare resulting solution with optimal makespan L*.Lemma 1. The optimal makespan L* maxjtj. Pf. Some machine must process the most time-consuming job. Lemma 2. The optimal makespan Pf. ?The total
9、processing time is j tj .?One of m machines must do at least a 1/m fraction of total work. L* 1 mtjj.9Load Balancing: Greedy Scheduling AnalysisTheorem. Greedy algorithm is a 2-approximation. Pf. Consider max load Liof bottleneck machine i.?Let j be last job scheduled on machine i.?When job j assign
10、ed to machine i, i had smallest load. Its load before assignment is Li - tj Li - tj Lk for all 1 k m.j0L = LiLi - tj machine iblue jobs scheduled before j410Load Balancing: Greedy Scheduling AnalysisTheorem. Greedy algorithm is a 2-approximation. Pf. Consider max load Liof bottleneck machine i.?Let
11、j be last job scheduled on machine i.?When job j assigned to machine i, i had smallest load. Its load before assignment is Li - tj Li - tj Lk for all 1 k m.?Sum inequalities over all k and divide by m:?NowLi tj1 mLkk =1 mtkk L*Li = (Litj) L*1 2 4 3 4 + tj L* 2L*.Lemma 2Lemma 111Load Balancing: Greed
12、y Scheduling AnalysisQ. Is our analysis tight? A. Essentially yes.Ex: m machines, m(m-1) jobs length 1 jobs, one job of length m Greedy solution = 2m-1; machine 2 idlemachine 3 idlemachine 4 idlemachine 5 idlemachine 6 idlemachine 7 idlemachine 8 idlemachine 9 idlemachine 10 idlelist scheduling make
13、span = 19m = 1012Load Balancing: List Scheduling AnalysisQ. Is our analysis tight? A. Essentially yes.Ex: m machines, m(m-1) jobs length 1 jobs, one job of length m?Greedy solution = 2m-1; Optimal makespan = m; = 2-1/m.m = 10optimal makespan = 10513Load Balancing: LPT RuleLongest processing time (LP
14、T). Sort n jobs in descending order of processing time, and then run Greedy scheduling algorithm.LPT-Greedy-Scheduling(m, n, t1,t2,tn) Sort jobs so that t1 t2 tnfor i = 1 to m Li 0 J(i) for j = 1 to n i = argminkLk J(i) J(i) j Li Li + tj return J(1), , J(m) jobs assigned to machine iload on machine
15、imachine i has smallest loadassign job j to machine iupdate load of machine i14Load Balancing: LPT RuleObservation. If at most m jobs, then greedy-scheduling is optimal. Pf. Each job put on its own machine. Lemma 3. If there are more than m jobs, L* 2tm+1. Pf. ?Consider first m+1 jobs t1, , tm+1.?Since the tis are in descending order, each takes at least tm+1time. ?There are m+1 jobs and m machines, so by pigeonhole principle, at least one machine gets two jobs. Theorem. LPT rule is a 3/2 approximation algorithm. Pf. Same basic approach as for the first
