MIT OpenCourseWarehttp://ocw.mit.edu 6.854J / 18.415J Advanced Algorithms Fall 2008��For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.18.415/6.854 Advanced Algorithms December 3, 2001 Lecture 21 Lecturer: Michel X. Goemans 1 Polynomial Approximation Schemes Definition 1 Polynomial Approximation Scheme (PAS) is a family of approximation algo- rithms such that A, E {A, :t > 0) runs in polynomial time in the size of the input (assume E fixed) and returns a 1+E approximate solution. Definition 2 A Fully Polynomial Approximation Algorithm (F'PAS) is a family of algo- rithms such that A, is a (1+E)-approximation algorithm with running time polynomial in input size and 1/~. 2 Scheduling Problem: PI1C,,, Definition 3 The Scheduling Problem (PIICmax):Given n jobs and m machines where each job j takes pj processing time and completes at time cj, assign jobs to each machine minimizing the time Cmaxfor the last machine to terminate its last job. Cmax=T*= min max cj 3 2.1 The Approach Definition 4 A (1+t) relaxed decision procedure for PI1 Cmax is an algorithm that, given T, either says that there is no schedule with Cmax5 T or gives a schedule with Cmax5 T(l+t) Initially T* is between L and 2L, where L = max(~z,maxpj), so let Tl and T2 be L and 2L respectively. We're now going to do a logarithmic binary search on the possible values for T* until we are within E of T*. Logarithmic Binary Search: If we know that T* is between Tl and T2, the next value we will check is dm,which is the midpoint of Tl and T2on the logarithmic scale. If our (1+E) relaxed decision procedure returns NO on dm,we replace T2with dm else we replace Tl with dm and continue until we are within E of T*. Initially, 2= 2. After k iterations, log T2 -log TI =2-k log 2. So if we want 2 5 1+E', 2k log 2/ log(l+ E') ,k log(1og 2/ log(1+el)). So, with k iterations, where k = O(1og $), we can get TI and Tz with properties: T2 /TI 5 1+E' ,there is no schedule with Cmax5 TI, and we have a schedule with Cmax5 T2(l+et) or T2(l+~/2)5 Tl(I+€') (1+~/2)5 TI(I+€). 2.2 A Relaxed Decision Definition 5 A (1+t) relaxed decision procedure for Pll Cmax is an algorithm that, given T, either says that there is no schedule with Cmax5 T or gives a schedule with Cmax5 T(l+ E)Remark 1 In the preceding definition, it is possible that the procedure returns NO, when a schedule does exist for Cmax< T(1+E). We will use a relaxed decision procedure to solve the scheduling problem. Suppose that we have a (1+€)-relaxed decision procedure for jobs with pj 1tT. Then we do the following: 1. Remove all jobs with pj < ET. 2. Apply the (1+€)-relaxed decision procedure for the remaining jobs. 3. If the procedure returns NO, we return NO. If we get a YES, use any method to try to add in all of the small jobs without going beyond T(1+ t). If we can, return that schedule else return NO. It is clear that if there is no schedule satisfying Cmaz5 T on some subset of the jobs, then we cannot hope for one on all of the jobs. Also if we cannot include a job pi < ET then that implies that each machine is busy at time T(1+E) -pi > T, so there can obviously be no schedule that finishes in time T. Consider a (1+E) relaxed decision procedure for the case where 'dpj 2 ET. We want to round pj to a qj that is of the form ET+~E~Tfor some integer k, that is Then pj satisfies the following inequality: 0 5 pj -qj < E~T.We output in polynomial time a schedule for {qj} with Cmax5 T or else say NO. NO: return NO. YES: return schedule. We can do this because ET5 pj +-qj 2ET+-There are at most $ jobs per machine. Therefore Cmaxincreases by at most ~(E~T)= ET. Now consider instances in which there are at most P jobs per machine and at most Q different processing times. In the above case, we take P = $ and Q = $. The problem is to find a schedule with Cmax5 T or claim that no such schedule exists, in polynomial time. Let (rl,...,rQ)be an assignment of jobs on a single machine. Each ri is the number of jobs of value pi in the assignment. Let the space of all valid assignments be We define a function f : +N,such that f (al,...,nQ) is the minimum number of machines needed to process ni jobs of value pi, i E (1, ... ,Q) within time T. f (nl, ...,nQ) = 1+min f (nl -rl, ...,n~ -r~)rER where 0 < ni < iti = number of jobs of processing time pi. We know that IRI 5 PQand i{(nl,. ..,nQ}I < nQ. By hypothesis, both of these bounds 1 1 are constant. Therefore the total running time is 0(nQ~)= 0(nQpQ)= 0(n~$2).This is polynomial for fixed
View Full Document