近似演算法
Introduction to Approximation Algorithms
| 節 | 週五 |
|---|---|
5 13:20–14:10 | 近似演算法 EC016（光復） 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 specific 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 • 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 • 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/113-1-approx
Linear Algebra, Probability, Algorithms
無備註
教師未提供此項資料
Handwritten Homework: 30% Final Exam: 30% Book Chapter Report and Presentation: 20% Paper Presentation: 20%
教師未提供此項資料
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction, The vertex cover problem and a 2-approximation, The set cover problem and an Hn-approximation |
| 第 2 週 | Approximation Schemes, FPTAS for the Knapsack Problem, Existence of FPTAS, PTAS for Scheduling on Identical Parallel Machines |
| 第 3 週 | Approximate-or-Refute and Parametric Search, The k-center problem and a 2-approximation |
| 第 4 週 | (MST-based algorithms) Steiner Tree Problem and a 2-approximation, Traveling Salesman Problem (TSP) and a 3/2-approximation, The Minimum Cycle Cover Problem |
| 第 5 週 | TBA |
| 第 6 週 | Introduction to LP-based Methods, Basic Threshold rounding, Randomized Rounding |
| 第 7 週 | Linear Programming Duality, The Weak Duality Theorem and Complementary Slackness, The Dual-Fitting scheme |
| 第 8 週 | Extreme Point Structure of Linear Polytopes, Half-integrality of vertex cover, Unrelated machine scheduling and a 2-approximation |
| 第 9 週 | The Iterative Rounding Technique, The Steiner Forest Problem and a 2-approximation, The Steiner Network Problem (Survival Network Design) and a 2-approximation |
| 第 10 週 | The Lift-and-Project Method and LP Hierarchies |
| 第 11 週 | Semidefinite Programming (SDP), The max-cut problem and a 0.878-approximation |
| 第 12 週 | The Hardness of Approximation Hardness via NP-hard reduction, The PCP theorem & The Unique Game Conjecture |
| 第 13 週 | (Supplements)Fundamental Theorem for Linear Inequalities,Strong LP Duality |
| 第 14 週 | Final Exam |
| 第 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