Report

Approximation Through Scaling Algorithms and Networks 2014/2015 Hans L. Bodlaender Johan M. M. van Rooij 1 C-approximation Optimization problem: output has a value that we want to maximize or minimize An algorithm A is an C-approximation algorithm, if for all inputs X, we have that (with OPT the optimal value) value(A(X)) / OPT ≤ C (minimisation), or OPT / value(A(X)) ≤ C (maximisation) 2 PTAS A Polynomial Time Approximation Scheme is an algorithm, that gets two inputs: the “usual” input X, and a real value e>0. For each fixed e>0, the algorithm Uses polynomial time Is an (1+e)-approximation algorithm 3 FPTAS A Fully Polynomial Time Approximation Scheme is an algorithm, that gets two inputs: the “usual” input X, and a real value e>0, and For each fixed e>0, the algorithm Is an (1+e)-approximation algorithm The algorithm uses time that is polynomial in the size of X and 1/e. 4 Example: Knapsack Given: n items each with a positive integer weight w(i) and integer value v(i) (1 ≤ i ≤ n), and an integer B. Question: select items with total weight at most B such that the total value is as large as possible. 5 Dynamic Programming for Knapsack Let P be the maximum value of all items. We can solve the problem in O(n2P) time with dynamic programming: Tabulate M(i,Q): minimum total weight of a subset of items 1, …, i with total value Q for Q at most nP M(0,0) = 0 M(0,Q) = ∞, if Q>0 M(i+1,Q) = min{ M(i,Q), M(i,Q-v(i+1)) + w(i+1) } 6 Scaling for Knapsack Take input for knapsack Throw away all items that have weight larger than B (they 7 are never used) Let c be some constant Build new input: do not change weights, but set new values v’(i) = v(i) / c Solve scaled instance with DP optimally Output this solution: approximates solution for original instance The Question is…. How do we set c, such that Approximation ratio good enough Polynomial time 8 Approximation ratio Consider optimal solution Y for original problem, value OPT Value in scaled instance: at least OPT/c – n At most n items, for each v(i)/c - v(i)/c <1 So, DP finds a solution of value at least OPT/c –n for scaled problem So, value of approximate solution for original instance is at least c*(OPT/c –n) = OPT - nc 9 Setting c Set c = eP/(2n) This is a FPTAS Running time: Largest value of an item is at most P/c = P / (eP/(2n)) = 2n/e . Running time is O(n2 * 2n/e) = O(n3/e) Approximation: … next 10 e-approximation Note that each item is a solution (we removed items with weight more than B). So OPT ≥ P. Algorithm gives solution of value at least: OPT – nc = OPT – n(e P / (2n) ) = OPT – e/2 P OPT / (OPT – e/2 P) ≤ OPT / (OPT – e/2 OPT) = 1/(1-e/2) ≤ 1+e 11 Comments Technique works for many problems .. But not always … 12