Question? Leave a message!




APPROXIMATION ALGORITHMS

APPROXIMATION ALGORITHMS
11. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣ Lecture slides by Kevin Wayne
 Copyright © 2005 PearsonAddison Wesley
 http://www.cs.princeton.edu/wayne/kleinbergtardos Last updated on 2/15/17 6:00 PMCoping with NPcompleteness Q. Suppose I need to solve an NPhard problem. What should I do 
 A. Sacrifice one of three desired features. i. Solve arbitrary instances of the problem. ii. Solve problem to optimality. iii. Solve problem in polynomial time. ρapproximation algorithm. Guaranteed to run in polytime. Guaranteed to solve arbitrary instance of the problem Guaranteed to find solution within ratio ρ of true optimum. Challenge. Need to prove a solution's value is close to optimum,
 without even knowing what optimum value is 211. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣Load balancing Input. m identical machines; n jobs, job j has processing time t . j 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 L = Σ t . ∈ i j J(i) j Def. The makespan is the maximum load on any machine L = max L . i i Load balancing. Assign each job to a machine to minimize makespan. machine 1 a d f Machine 1 b c Machine 2 e g machine 2 0 time L L 2 1 4Load balancing on 2 machines is NPhard Claim. Load balancing is hard even if only 2 machines. Pf. PARTITION ≤ LOADBALANCE. P NPcomplete by Exercise 8.26 a b c d e f g length of job f machine 1 a d f Machine 1 yes b c Machine 2 e g machine 2 0 time L 5Load balancing: list scheduling Listscheduling algorithm. Consider n jobs in some fixed order. Assign job j to machine whose load is smallest so far. ListScheduling(m, n, t ,t ,…,t ) 1 2 n for i = 1 to m L ← 0 load on machine i i J(i) ← ∅ jobs assigned to machine i for j = 1 to n machine i has smallest load i = argmin L k k assign job j to machine i J(i) ← J(i) ∪ j update load of machine i L ← L + t i i j return J(1), …, J(m) Implementation. O(n log m) using a priority queue. 6Load balancing: list scheduling analysis Theorem. Graham 1966 Greedy algorithm is a 2approximation. First worstcase analysis of an approximation algorithm. Need to compare resulting solution with optimal makespan L. Lemma 1. The optimal makespan L ≥ max t . j j Pf. Some machine must process the most timeconsuming job. ▪ 1 Lemma 2. The optimal makespan L ≥ t . ∑ j j m Pf. The total processing time is Σ t . j j One of m machines must do at least a 1 / m fraction of total work. ▪ € 7Believe it or not 1 L ≥ t . ∑ j j m € 8Load balancing: list scheduling analysis Theorem. Greedy algorithm is a 2approximation. Pf. Consider load L of bottleneck machine i. i Let j be last job scheduled on machine i. When job j assigned to machine i, i had smallest load.
 Its load before assignment is L – t ⇒ L – t ≤ L for all 1 ≤ k ≤ m. i j i j k blue jobs scheduled before j j machine i 0 time L = L L t i i j 9Load balancing: list scheduling analysis Theorem. Greedy algorithm is a 2approximation. Pf. Consider load L of bottleneck machine i. i Let j be last job scheduled on machine i. When job j assigned to machine i, i had smallest load.
 Its load before assignment is L – t ⇒ L – t ≤ L for all 1 ≤ k ≤ m. i j i j k Sum inequalities over all k and divide by m: 1 L − t ≤ L ∑ i j k k m 1 = t ∑ k m k Lemma 2 ≤ L Now, L = ▪ L = (L −t ) + t ≤ 2L . i i j j " € ≤ L ≤ L Lemma 1 € 10Load balancing: list scheduling analysis Q. Is our analysis tight A. Essentially yes. Ex: m machines, m (m – 1) jobs length 1 jobs, one job of length m. list scheduling makespan = 19 = 2m 1 machine 2 idle machine 3 idle machine 4 idle m = 10 machine 5 idle machine 6 idle machine 7 idle machine 8 idle machine 9 idle machine 10 idle 0 9 19 11Load balancing: list scheduling analysis Q. Is our analysis tight A. Essentially yes. Ex: m machines, m (m – 1) jobs length 1 jobs, one job of length m. optimal makespan = 10 = m m = 10 0 9 10 19 12Load balancing: LPT rule Longest processing time (LPT). Sort n jobs in descending order of processing time, and then run list scheduling algorithm. LPTListScheduling(m, n, t ,t ,…,t ) 1 2 n Sort jobs so that t ≥ t ≥ … ≥ t 1 2 n for i = 1 to m L ← 0 load on machine i i jobs assigned to machine i J(i) ← ∅ for j = 1 to n machine i has smallest load i = argmin L k k assign job j to machine i J(i) ← J(i) ∪ j update load of machine i L ← L + t i i j return J(1), …, J(m) 13Load balancing: LPT rule Observation. If at most m jobs, then listscheduling is optimal. Pf. Each job put on its own machine. ▪ Lemma 3. If there are more than m jobs, L ≥ 2 t . m+1 Pf. Consider first m+1 jobs t , …, t . 1 m+1 Since the t 's are in descending order, each takes at least t time. i m+1 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/2approximation algorithm. Pf. Same basic approach as for list scheduling. 3 L = (L − t ) + t ≤ L . i i j j 2 ▪ " 1 ≤ L ≤ L 2 Lemma 3
 ( by observation, can assume number of jobs m ) 14 € Load Balancing: LPT rule Q. Is our 3/2 analysis tight A. No. Theorem. Graham 1969 LPT rule is a 4/3approximation. Pf. More sophisticated analysis of same algorithm. Q. Is Graham's 4/3 analysis tight A. Essentially yes. Ex. m machines n = 2m + 1 jobs 2 jobs of length m, m + 1, …, 2m – 1 and one more job of length m. Then, L / L = (4m − 1) / (3m) 1511. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣Center selection problem Input. Set of n sites s , …, s and an integer k 0. 1 n Center selection problem. Select set of k centers C so that maximum distance r(C) from a site to nearest center is minimized. k = 4 centers r(C) center site 17Center selection problem Input. Set of n sites s , …, s and an integer k 0. 1 n Center selection problem. Select set of k centers C so that maximum distance r(C) from a site to nearest center is minimized. Notation. dist(x, y) = distance between sites x and y. dist(s , C) = min dist(s , c) = distance from s to closest center. ∈ i c C i i r(C) = max dist(s , C) = smallest covering radius. i i Goal. Find set of centers C that minimizes r(C), subject to C = k. Distance function properties. dist(x, x) = 0 identity dist(x, y) = dist(y, x) symmetry dist(x, y) ≤ dist(x, z) + dist(z, y) triangle inequality 18Center selection example Ex: each site is a point in the plane, a center can be any point in the plane, dist(x, y) = Euclidean distance. Remark: search can be infinite k = 4 centers r(C) center site 19Greedy algorithm: a false start Greedy algorithm. Put the first center at the best possible location for a single center, and then keep adding centers so as to reduce the covering radius each time by as much as possible. Remark: arbitrarily bad k = 2 centers greedy center 1 center site 20Center selection: greedy algorithm Repeatedly choose next center to be site farthest from any existing center. GREEDYCENTERSELECTION (k, n, s , s , … , s ) 1 2 n 
 C ← ∅. REPEAT k times Select a site s with maximum distance dist(s , C). i i C ← C ∪ s . i site farthest RETURN C. from any center 
 
 Property. Upon termination, all centers in C are pairwise at least r(C) apart. Pf. By construction of algorithm. 21Center selection: analysis of greedy algorithm Lemma. Let C be an optimal set of centers. Then r(C) ≤ 2r(C). Pf. by contradiction Assume r(C) ½ r(C). For each site c ∈ C, consider ball of radius ½ r(C) around it. i Exactly one c in each ball; let c be the site paired with c . i i i Consider any site s and its closest center c ∈ C. i dist(s, C) ≤ dist(s, c ) ≤ dist(s, c ) + dist(c , c ) ≤ 2r(C). i i i i Thus, r(C) ≤ 2r(C). ▪ ≤ r(C) since c is closest center i Δinequality ½ r(C) ½ r(C) c i ½ r(C) C c i s site 22Center selection Lemma. Let C be an optimal set of centers. Then r(C) ≤ 2r (C). Theorem. Greedy algorithm is a 2approximation for center selection problem. Remark. Greedy algorithm always places centers at sites, but is still within a factor of 2 of best solution that is allowed to place centers anywhere. 
 e.g., points in the plane 
 
 Question. Is there hope of a 3/2approximation 4/3 23Dominating set reduces to center selection Theorem. Unless P = NP, there no ρapproximation for center selection
 problem for any ρ 2. Pf. We show how we could use a (2 – ε) approximation algorithm for
 CENTERSELECTION selection to solve DOMINATINGSET in polytime. Let G = (V, E), k be an instance of DOMINATINGSET. Construct instance G' of CENTERSELECTION with sites V and distances dist(u, v) = 1 if (u, v) ∈ E dist(u, v) = 2 if (u, v) ∉ E Note that G' satisfies the triangle inequality. G has dominating set of size k iff there exists k centers C with r(C) = 1. Thus, if G has a dominating set of size k, a (2 – ε)approximation algorithm for CENTERSELECTION would find a solution C with r(C) = 1 since it cannot use any edge of distance 2. ▪ 2411. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣Weighted vertex cover Definition. Given a graph G = (V, E), a vertex cover is a set S ⊆ V such that each edge in E has at least one end in S. Weighted vertex cover. Given a graph G with vertex weights, find a vertex cover of minimum weight. 2 4 2 4 2 9 2 9 weight = 11 weight = 2 + 2 + 4 26Pricing method Pricing method. Each edge must be covered by some vertex. 
 Edge e = (i, j) pays price p ≥ 0 to use both vertex i and j. e Fairness. Edges incident to vertex i should pay ≤ w in total. i 2 4 for each vertex i : p ≤ w ∑ e i e=(i,j) 2 9 € Fairness lemma. For any vertex cover S and any fair prices p : ∑ p ≤ w(S). e e e Pf. ▪ each edge e covered by
 sum fairness inequalities
 at least one node in S for each node in S 27Pricing method Set prices and find vertex cover simultaneously. WEIGHTEDVERTEXCOVER (G, w) S ← ∅. FOREACH e ∈ E p ← 0.
 e WHILE (there exists an edge (i, j) such that neither i nor j is tight) Select such an edge e = (i, j). Increase p as much as possible until i or j tight.
 e 
 S ← set of all tight nodes. RETURN S. 28Pricing method example price of edge ab vertex weight 29Pricing method: analysis Theorem. Pricing method is a 2approximation for WEIGHTEDVERTEXCOVER. Pf. Algorithm terminates since at least one new node becomes tight after each iteration of while loop. Let S = set of all tight nodes upon termination of algorithm.
 S is a vertex cover: if some edge (i, j) is uncovered, then neither i nor j
 is tight. But then while loop would not terminate. Let S be optimal vertex cover. We show w(S) ≤ 2 w(S). w(S) = w = p ≤ p = 2 p ≤ 2w(S). ∑ ∑ ∑ ∑ ∑ ∑ i e e e i∈S i∈S e=(i,j) i∈V e=(i,j) e∈E fairness lemma all nodes in S are tight S ⊆ V,
 each edge counted twice prices ≥ 0 € 3011. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣Weighted vertex cover Given a graph G = (V, E) with vertex weights w ≥ 0, find a min weight subset i of vertices S ⊆ V such that every edge is incident to at least one vertex in S. 10 9 6 16 10 7 6 9 3 23 33 7 32 10 total weight = 6 + 9 + 10 + 32 = 57 32Weighted vertex cover: ILP formulation Given a graph G = (V, E) with vertex weights w ≥ 0, find a min weight subset i of vertices S ⊆ V such that every edge is incident to at least one vertex in S. Integer linear programming formulation. Model inclusion of each vertex i using a 0/1 variable x .
 i 
 " 0 if vertex i is not in vertex cover x = 
 i 1 if vertex i is in vertex cover 
 Vertex covers in 1–1 correspondence with 0/1 assignments:
 S = i ∈ V : x = 1. i € Objective function: minimize Σ w x . i i i For every edge (i, j), must take either vertex i or j (or both): x + x ≥ 1. i j 33Weighted vertex cover: ILP formulation Weighted vertex cover. Integer linear programming formulation. (ILP)KBM w x i i i V bXiX x +x 1 (i,j) E i j x 0, 1 i V i Observation. If x is optimal solution to (ILP), then S = i ∈ V : x = 1
 i is a min weight vertex cover. 34Integer linear programming Given integers a , b , and c , find integers x that satisfy: ij i j j n T KBM c x KBM c x j j j=1 bXiX Ax b n x 0 bXiX a x b 1 i m ij j i xi2;`HBM j=1 x 0 1 j n j 
 xi2;`HBM 1 j n j 
 Observation. Vertex cover formulation proves that INTEGERPROGRAMMING
 is an NPhard search problem. 35Linear programming Given integers a , b , and c , find real numbers x that satisfy:
 ij i j j 
 
 n T KBM c x KBM c x j j 
 j=1 bXiX Ax b n 
 x 0 bXiX a x b 1 i m ij j i xi2;`HBM j=1 x 0 1 j n j xi2;`HBM 1 j n j 2 Linear. No x , xy, arccos(x), x(1 – x), etc. Simplex algorithm. Dantzig 1947 Can solve LP in practice. Ellipsoid algorithm. Khachian 1979 Can solve LP in polytime.
 Interior point algorithms. Karmarkar 1984, Renegar 1988, … Can solve LP in polytime and in practice. 36LP feasible region LP geometry in 2D. x = 0 1 x = 0 2 x + 2x = 6 1 2 2x + x = 6 1 2 37Weighted vertex cover: LP relaxation Linear programming relaxation. (LP)KBM w x i i i V bXiX x +x 1(i,j) E i j x 0 i V i Observation. Optimal value of (LP) is ≤ optimal value of (ILP).
 Pf. LP has fewer constraints. ½ ½ Note. LP is not equivalent to vertex cover. ½ Q. How can solving LP help us find a small vertex cover A. Solve LP and round fractional values. 38Weighted vertex cover: LP rounding algorithm Lemma. If x is optimal solution to (LP), then S = i ∈ V : x ≥ ½ is a
 i vertex cover whose weight is at most twice the min possible weight. Pf. S is a vertex cover Consider an edge (i, j) ∈ E. Since x + x ≥ 1, either x ≥ ½ or x ≥ ½ (or both) ⇒ (i, j) covered. i j i j Pf. S has desired cost Let S be optimal vertex cover. Then 1 w ≥ w x ≥ w ∑ ∑ ∑ i i i i 2 i∈ S i∈ S i∈ S LP is a relaxation x ≥ ½ i € Theorem. The rounding algorithm is a 2approximation algorithm. Pf. Lemma + fact that LP can be solved in polytime. 39Weighted vertex cover inapproximability Theorem. Dinur–Safra 2004 If P ≠ NP, then no ρapproximation for WEIGHTEDVERTEXCOVER for any ρ 1.3606 (even if all weights are 1). On the Hardness of Approximating Minimum Vertex Cover 
 ∗ † Irit Dinur Samuel Safra 
 May 26, 2004 
 
 Abstract 
 We prove the Minimum Vertex Cover problem to be NPhard to approximate to within a factor of 1.3606, extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and borrow and extend ideas from 
 several fields. 
 1 Introduction 
 The basic purpose of Computational Complexity Theory is to classify computational problems according to the amount of resources required to solve them. In particular, the most basic task 
 is to classify computational problems to those that are efficiently solvable and those that are not. The complexity class P consists of all problems that can be solved in polynomialtime. It Open research problem. Close the gap. is considered, for this rough classification, as the class of efficientlysolvable problems. While many computational problems are known to be in P, many others, are neither known to be in P, nor proven to be outside P. Indeed many such problems are known to be in the class NP, namely the class of all problems whose solutions can be verified in polynomialtime. When it comes to proving that a problem is outside a certain complexity class, current techniques are 40 radically inadequate. The most fundamental open question of Complexity Theory, namely, the P vs. NP question, may be a particular instance of this shortcoming. While the P vs NP question is wide open, one may still classify computational problems into those in P and those that are NPhard Coo71, Lev73, Kar72. A computational problem L is NPhard if its complexity epitomizes the hardness of NP. That is, any NP problem can be efficiently reduced to L. Thus, the existence of a polynomialtime solution for L implies P=NP. Consequently, showing P̸=NP would immediately rule out an efficient algorithm for any NP hard problem. Therefore, unless one intends to show NP=P, one should avoid trying to come up with an efficient algorithm for an NPhard problem. Letusturnourattentiontoaparticulartypeofcomputationalproblems,namely,optimization problems — where one looks for an optimal among all plausible solutions. Some optimization problems are known to be NPhard, for example, finding a largest size independent set in a graph Coo71, Kar72, or finding an assignment satisfying the maximum number of clauses in a given 3CNF formula (MAX3SAT) Kar72. ∗ The Miller Institute, UC Berkeley. Email: iritdcs.berkeley.edu. † School of Mathematics and School of Computer Science, Tel Aviv University and The Miller Institute, UC Berkeley. Research supported in part by the Fund for Basic Research administered by the Israel Academy of Sciences, and a Binational USIsraeli BSF grant. Email: saframath.tau.ac.il. 111. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣Generalized load balancing Input. Set of m machines M; set of n jobs J. Job j ∈ J must run contiguously on an authorized machine in M ⊆ M. j Job j ∈ J has processing time t . j Each 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 L = Σ t . ∈ i j J(i) j Def. The makespan is the maximum load on any machine = max L . i i Generalized load balancing. Assign each job to an authorized machine to minimize makespan. 42Generalized load balancing: integer linear program and relaxation ILP formulation. x = time machine i spends processing job j. ij (IP) min L s. t. x = t for all j∈ J ∑ ij j i x ≤ L for all i∈ M ∑ ij j x ∈ 0, t for all j∈ J and i∈ M ij j j x = 0 for all j∈ J and i∉ M ij j LP relaxation. € (LP) min L s. t. x = t for all j∈ J ∑ ij j i x ≤ L for all i∈ M ∑ ij j x ≥ 0 for all j∈ J and i∈ M ij j x = 0 for all j∈ J and i∉ M ij j 43 € Generalized load balancing: lower bounds Lemma 1. The optimal makespan L ≥ max t . j j Pf. Some machine must process the most timeconsuming job. ▪ Lemma 2. Let L be optimal value to the LP. Then, optimal makespan L ≥ L. Pf. LP has fewer constraints than IP formulation. ▪ 44Generalized load balancing: structure of LP solution Lemma 3. Let x be solution to LP. Let G(x) be the graph with an edge between machine i and job j if x 0. Then G(x) is acyclic. ij can transform x into another LP solution where
 Pf. (deferred) G(x) is acyclic if LP solver doesn't return such an x x 0 ij G(x) acyclic G(x) cyclic job machine 45Generalized load balancing: rounding Rounded solution. Find LP solution x where G(x) is a forest. Root forest G(x) at some arbitrary machine node r. If job j is a leaf node, assign j to its parent machine i. If job j is not a leaf node, assign j to any one of its children. Lemma 4. Rounded solution only assigns jobs to authorized machines. Pf. If job j is assigned to machine i, then x 0. LP solution can only assign ij positive value to authorized machines. ▪ job machine 46Generalized load balancing: analysis Lemma 5. If job j is a leaf node and machine i = parent(j), then x = t . ij j Pf. Since i is a leaf, x = 0 for all j ≠ parent(i). ij LP constraint guarantees Σ x = t . ▪ i ij j Lemma 6. At most one nonleaf job is assigned to a machine. Pf. The only possible nonleaf job assigned to machine i is parent(i). ▪ job machine 47Generalized load balancing: analysis Theorem. Rounded solution is a 2approximation. Pf. Let J(i) be the jobs assigned to machine i. By LEMMA 6, the load L on machine i has two components: i LP Lemma 2 (LP is a relaxation) leaf nodes: Lemma 5 t = x ≤ x ≤ L ≤ L ∑ ∑ ∑ j ij ij j ∈ J(i) j ∈ J(i) j ∈ J j is a leaf j is a leaf optimal value of LP Lemma 1 € parent: t ≤ L parent(i) € Thus, the overall load L ≤ 2 L. ▪ i 48Generalized load balancing: flow formulation Flow formulation of LP. ∞ x = t for all j∈ J ∑ ij j i x ≤ L for all i∈ M ∑ ij j x ≥ 0 for all j∈ J and i∈ M ij j x = 0 for all j∈ J and i∉ M ij j € Observation. Solution to feasible flow problem with value L are in
 1to1 correspondence with LP solutions of value L. 49Generalized load balancing: structure of solution Lemma 3. Let (x, L) be solution to LP. Let G(x) be the graph with an edge from machine i to job j if x 0. We can find another solution (x', L) such that ij G(x') is acyclic. Pf. Let C be a cycle in G(x). flow conservation maintained Augment flow along the cycle C. At least one edge from C is removed (and none are added). Repeat until G(x') is acyclic. ▪ augment flow along cycle C 3 3 3 3 6 6 2 3 4 4 2 1 5 5 1 3 4 4 4 G(x) G(x') 50Conclusions Running time. The bottleneck operation in our 2approximation is
 solving one LP with m n + 1 variables. Remark. Can solve LP using flow techniques on a graph with m + n + 1 nodes: given L, find feasible flow if it exists. Binary search to find L. Extensions: unrelated parallel machines. Lenstra–Shmoys–Tardos 1990 Job j takes t time if processed on machine i. ij 2approximation algorithm via LP rounding. If P ≠ NP, then no no ρapproximation exists for any ρ 3/2. Mathematical Programming 46 (1990) 259271 259 NorthHolland APPROXIMATION ALGORITHMS FOR SCHEDULING UNRELATED PARALLEL MACHINES Jan Karel LENSTRA Eindhoven University of Technology, Eindhoven, The Netherlands, and Centre for Mathematics and Computer Science, Amsterdam, The Netherlands David B. SHMOYS and lva TARDOS Cornell University, Ithaca, NY, USA 51 Received 1 October 1987 Revised manuscript 26 August 1988 We consider the following scheduling problem. There are m parallel machines and n independent .jobs. Each job is to be assigned to one of the machines. The processing of .job j on machine i requires time Pip The objective is to lind a schedule that minimizes the makespan. Our main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. We also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, we give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints. In contrast to our main result, we prove that no polynomial algorithm can achieve a worstcase ratio less than unless P = NIL We finally obtain a complexity classification for all special cases with a fixed number of processing times. Key words: Scheduling, parallel machines, approximation algorithm, worst case analysis, linear programming, integer programming, rounding. 1. Introduction Although the performance of approximation algorithms has been studied for over twenty years, very little is understood about the structural properties of a problem that permit good performance guarantees. In fact, there are practically no tools to distinguish those problems for which there does exist a polynomial algorithm for any performance bound, and those for which this is not the case. One problem area in which these questions have received much attention is that of scheduling and bin packing. We examine a scheduling problem for which all previously analyzed polynomial algorithms have particularly poor performance guarantees. We present A preliminary version of this paper appeared in the Proceedings cf the 28th Annual lEEK Symposium on the Foundations of Computer Stience (Computer Society Press of the lEEK, Washington, I).C., 1987) pp. 217 224. 11. APPROXIMATION ALGORITHMS load balancing ‣ center selection ‣ pricing method: vertex cover ‣ LP rounding: vertex cover ‣ generalized load balancing ‣ knapsack problem ‣Polynomialtime approximation scheme PTAS. (1 + ε)approximation algorithm for any constant ε 0. Load balancing. Hochbaum–Shmoys 1987 Euclidean TSP. Arora, Mitchell 1996 Consequence. PTAS produces arbitrarily high quality solution,
 but trades off accuracy for time. This section. PTAS for knapsack problem via rounding and scaling. 53Knapsack problem Knapsack problem. Given n objects and a knapsack. we assume w ≤ W for each i Item i has value v 0 and weighs w 0. i i i Knapsack has weight limit W. Goal: fill knapsack so as to maximize total value. Ex: 3, 4 has value 40. item value weight 1 1 1 2 6 2 3 18 5 4 22 6 5 28 7 original instance (W = 11) 54Knapsack is NPcomplete KNAPSACK. Given a set X, weights w ≥ 0, values v ≥ 0, a weight limit W, and a i i target value V, is there a subset S ⊆ X such that: 
 w ≤ W ∑ i 
 i∈S 
 v ≥ V ∑ i i∈S 
 SUBSETSUM. Given a set X, values u ≥ 0, and an integer U, is there a subset S i ⊆ X whose elements sum to exactly U € 
 Theorem. SUBSETSUM ≤ KNAPSACK. P Pf. Given instance (u , …, u , U) of SUBSETSUM, create KNAPSACK instance: 1 n v =w =u u ≤ U ∑ i i i i i∈S V =W =U u ≥ U ∑ i i∈S 55 € Knapsack problem: dynamic programming I Def. OPT(i, w) = max value subset of items 1,..., i with weight limit w. 
 Case 1. OPT does not select item i. OPT selects best of 1, …, i – 1 using up to weight limit w. 
 Case 2. OPT selects item i. New weight limit = w – w . i OPT selects best of 1, …, i – 1 using up to weight limit w – w . i 
 0 if i = 0 
 OPT(i, w) = OPT(i−1, w) if w w i 
 max OPT(i−1, w), v + OPT(i−1, w− w ) otherwise i i 
 
 Theorem. Computes the optimal value in O(n W) time. € Not polynomial in input size. Polynomial in input size if weights are small integers. 56Knapsack problem: dynamic programming II Def. OPT(i, v) = min weight of a knapsack for which we can obtain a solution of value ≥ v using a subset of items 1,..., i. 
 Note. Optimal value is the largest value v such that OPT(n, v) ≤ W. 
 Case 1. OPT does not select item i. OPT selects best of 1, …, i – 1 that achieves value ≥ v. 
 Case 2. OPT selects item i. Consumes weight w , need to achieve value ≥ v – v . i i OPT selects best of 1, …, i – 1 that achieves value ≥ v – v . i 0B7 v 0 OPT(i,v)= B7 i=0M/ v 0 min OPT(i 1,v),w +OPT(i 1,v v )Qi2`rBb2 i i 57Knapsack problem: dynamic programming II Theorem. Dynamic programming algorithm II computes the optimal value 2 in O(n v ) time, where v is the maximum of any value. max max Pf. The optimal value V ≤ n v . max There is one subproblem for each item and for each value v ≤ V. It takes O(1) time per subproblem. ▪ 
 Remark 1. Not polynomial in input size Remark 2. Polynomial time if values are small integers. 58Knapsack problem: polynomialtime approximation scheme Intuition for approximation algorithm. Round all values up to lie in smaller range. Run dynamic programming algorithm II on rounded/scaled instance. Return optimal items in rounded instance. item value weight item value weight 1 934221 1 1 1 1 2 5956342 2 2 6 2 3 17810013 5 3 18 5 4 21217800 6 4 22 6 5 27343199 7 5 28 7 original instance (W = 11) rounded instance (W = 11) 59Knapsack problem: polynomialtime approximation scheme Round up all values: 0 ε ≤ 1 = precision parameter. v v i i v = largest value in original instance. v¯ = , vˆ = max i i θ = scaling factor = ε v / 2n. max 
 
 Observation. Optimal solutions to problem with are equivalent to
 v v ˆ optimal solutions to problem with . 
 € Intuition. v close to v so optimal solution using is nearly optimal;
 v € small and integral so dynamic programming algorithm II is fast. v ˆ € € € 60Knapsack problem: polynomialtime approximation scheme Theorem. If S is solution found by rounding algorithm and S
 is any other feasible solution, then (1+ ) v v i i i S i S 
 Pf. Let S be any feasible solution satisfying weight constraint. subset containing always round up only the item v v¯ i i v v¯ i i of largest value i S i S v v¯ i i i S i S v v¯ i i i S i S v¯ v v¯ i i i solve rounded i S i S v¯ i i S instance optimally i S i S v¯ i i S v¯ i choosing S = max i S (v + ) v¯ ii i S (v + ) never round up i 11 ii S S (v + ) vv vv + + vv iKtKt iiKtKt 22 by more than θ 1 i S(v + ) i v v + v Kt iKt ii S S 2 i S (v + ) v + n i i i S i S 11 v + n i vv + + vv i S i S iiKtKt 22 v + n 1 i v + v i Sv + n S ≤ n iKt ii S S i 2 1 i S v + n = v + v i i max thus i S 21 i S vv 22vv = v + v KtKt ii i max 1 i S 2 i S = v + v v 2 v i max 1 Kt i ii S S 2 i S = v + v i max 1 2 i S i S = v + v θ = ε v / 2n iKt =(1+ ) v max 2 i i S =(1+ ) v i i S i S =(1+ ) v i i S =(1+ ) v i =(1+ ) v i S i v ≤ 2 Σ v i S max i ∈ S i (1+ ) v i i S i S 61Knapsack problem: polynomialtime approximation scheme Theorem. For any ε 0, the rounding algorithm computes a feasible solution 3 whose value is within a (1 + ε) factor of the optimum in O(n / ε) time. 
 Pf. We have already proved the accuracy bound. 2 O(n v ˆ ) Dynamic program II running time is , where max v 2n max € vˆ = = max 62
Website URL
Comment