近似演算法
Introduction to Approximation Algorithms
| 節 | 週四 |
|---|---|
5 13:20–14:10 | 近似演算法 ED102 2 節連堂 |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
This course aims to provide a technique-oriented introduction on the versatile approximation algorithms for various categories of NP-hard problems. We will cover the basic algorithm design & analysis techniques and use various problems and algorithms as examples. The students are expected to acquire a deeper understanding via group presentations on classic research papers. The problems that may arise in this course include the following: • Cover Problems - Vertex Cover / Dominating Set / Set Cover, Submodular Cover • Location / Clustering Problems - k-Center, k-Median, Facility Location • Packing / Scheduling Problems - Knapsack, Bin Packing, Unrelated / Identical Machine Scheduling • Flow / Cut / Routing Problems - Max Cut, Multiway Cut, Multi-Cut / Multi-Commodity Flow, Sparest Cut • Network Design Problems - Steiner Tree / Forest, Steiner Network Problem (Survival Network Design) • Tour Problems - Traveling Salesman Problem (TSP) Course website: https://sites.google.com/nycu.edu.tw/112-1-approx
Linear Algebra, Probability, Algorithms
The lectures will be given by premade video recordings (1~1.5hrs, to be played at class) with in-class explanations. Students are expected to read the prepared lecture notes and slides, in order to fully understand the concepts.
Handwritten Homework: 30% Midterm Exam: 30% Paper Presentation: 40%
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction |
| 第 2 週 | FPTAS for the Knapsack Problem, Existence of FPTAS |
| 第 3 週 | (MST-based algorithms) Traveling Salesman Problem (TSP), A PTAS for TSP, Minimum Cycle Cover |
| 第 4 週 | The set cover problem and a (log n)-approximation, The vertex cover problem and an f-approximation |
| 第 5 週 | Approximate-or-Refute and Parametric Search The k-center problem and a 2-approximation |
| 第 6 週 | Introduction to LP-based Methods Threshold rounding |
| 第 7 週 | Extreme Point Structure of Linear Polytopes Half-integrality of vertex cover, Unrelated machine scheduling and a 2-approximation |
| 第 8 週 | Linear Programming Duality The Weak Duality Theorem, Complementary Slackness, Dual-Fitting scheme |
| 第 9 週 | (Tentative) The factor-revealing technique |
| 第 10 週 | Semidefinite Programming (SDP) The max-cut problem and a 0.878-approximation |
| 第 11 週 | The Hardness of Approximation Hardness via NP-hard reduction, The PCP theorem & The Unique Game Conjecture |
| 第 12 週 | (Supplements) Fundamental Theorem for Linear Inequalities, Strong LP Duality |
| 第 13 週 | Midterm Exam |
| 第 14 週 | Group presentation |
| 第 15 週 | Group presentation |
| 第 16 週 | Group presentation |
1. Approximation Algorithms, by Vijay Vazirani, Springer-Verlag, 2004. 2. The Design of Approximation Algorithms, by David Williamson and David Shmoys, Cambridge, 2012.
- 時間
- By appointment
- 聯絡方式
- mjkao@nycu.edu.tw