近似演算法
Introduction to Approximation Algorithms
| 節 | 週五 |
|---|---|
5 13:20–14:10 | 近似演算法 ED102 2 節連堂 |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
This course aims to provide an introduction on the versatile approximation algorithms for various categories of fundamental NP-hard problems. The lectures will cover the core algorithmic design & analysis techniques, and the students are expected to learn the concepts via group presentations on various representative algorithms for problems that may arise in practice. 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) We will examine classic approximation algorithms and state-of-the-art status for the above categories of problems, to the extent that fits the scope of this course. The lectures will be mostly technique-oriented with the algorithms being the examples. Throughout this course, students will pick up the classic techniques and hopefully learn to design and analyze their own approximation algorithms. Course website: https://sites.google.com/nycu.edu.tw/i2-approx-algo
Linear Algebra, Probability, Algorithms
Students are expected to read the prepared lecture notes and slides, in order to fully understand the concepts. The lectures will be given by premade video recordings (1~1.5hrs).
2-3 Handwritten Homework: 30% Open-book Final Exam: 20% Book Chapter & Paper Group Presentation: 60%
| 週次 | 主題 |
|---|---|
| 第 1 週 | * Introduction * Basic Concepts & Definitions |
| 第 2 週 | * Approximate to any Desirable Degree * FPTAS for the Knapsack Problem, Existence of FPTAS, Asymptotic PTAS for the Bin Packing Problem |
| 第 3 週 | * Greedy towards Cost-Efficiency * The set cover problem and a (log n)-approximation, The vertex cover problem and an f-approximation |
| 第 4 週 | * Approximate-or-Refute for Parametric Search * The k-center problem and a 2-approximation |
| 第 5 週 | * Introduction to LP-based Methods * The basic framework, Threshold rounding |
| 第 6 週 | * Extreme Point Structure of Linear Polytopes * Half-integrality of vertex cover, Unrelated machine scheduling and a 2-approximation |
| 第 7 週 | * Designing Better LP Relaxations * The multiway cut problem and a (2-2/k)-approximation |
| 第 8 週 | * Iterative Rounding * The Steiner network problem and a 2-approximation |
| 第 9 週 | * Complementing the Weak-Spots via Linear Combinations * Probabilistic Combination of Algorithms |
| 第 10 週 | * Linear Programming Duality * The Weak Duality Theorem, Complementary Slackness, Simple Dual-Fitting scheme |
| 第 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 |
| 第 15 週 | * Supplements * Fundamental Theorem for Linear Inequalities, Strong LP Duality |
| 第 16 週 | Final Exam |
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