New version page

MIT 6 854J - Polynomial Approximation Schemes

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

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
Download Polynomial Approximation Schemes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Polynomial Approximation Schemes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Polynomial Approximation Schemes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?