近似算法课件-负载均衡.pdf

Approximation Design and Analysis of Algorithms Andrei Bulatov Algorithms – Approximation 21-2 Approximation Algorithms Suppose I need to solve an NP-hard problem. What should I do? Theory says youre unlikely to find a poly-time algorithm. Must sacrifice one of three desired features. – Solve problem to optimality. –– Solve problem in polySolve problem in poly--time.time. – Solve arbitrary 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 value is! Algorithms – Approximation 21-3 Optimization Problems In an optimization problem, for every possible instance x we have: - a set S(x) of feasible solutions - for every solution y ∈ S(x), we a positive goodness m(x,y) - optimization parameter opt ∈ {min,max} To solve an optimization problem we must find for any given x ∈ I , a solution y ∈ S(x) such that m(x ,y ) = opt {m(x ,z ) | z ∈ S (x)} The optimal value will be denoted OPT(x) Algorithms – Approximation 21-4 Relative Error Sometimes it is sufficient to find an approximate solution The relative error of a solution y (with respect to an instance x) is | OPT(x) − m(x ,y ) | OPT(OPT(xx)) In a maximization problem m(x,y) is always smaller than OPT(x), so the relative error lies between 0 and 1 I