Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Algorithm design - Chapter 11: Approximation Algorithms

Chapter 11 "Approximation Algorithms" include all of the following: Load balancing, center selection, pricing method: vertex cover, LP rounding: vertex cover, generalized load balancing, knapsack problem. | Lecture slides by Kevin Wayne Copyright 2005 Pearson-Addison Wesley http www.cs.princeton.edu wayne kleinberg-tardos 11. Approximation Algorithms load balancing center selection pricing method vertex cover LP rounding vertex cover generalized load balancing knapsack problem Last updated on 10 17 15 9 44 AM Coping with NP-completeness Q. Suppose I need to solve an NP-hard 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. p-approximation algorithm. Guaranteed to run in poly-time. Guaranteed to solve arbitrary instance of the problem Guaranteed to find solution within ratio p of true optimum. Challenge. Need to prove a solution s value is close to optimum without even knowing what optimum value is 2 11. Approximation Algorithms load .