TAILIEUCHUNG - 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 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 .

TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.