近似演算法(英文授課)
Introduction to Approximation Algorithms
| 節 | 週五 |
|---|---|
6 14:20–15:10 | 近似演算法(英文授課) ED102 3 節連堂 |
7 15:30–16:20 | |
8 16:30–17:20 |
* 根據陽明交大上課時間表所列
Course website: https://sites.google.com/nycu.edu.tw/5981-i2-approx-algo In this course, we aim to examine approximation algorithms for various categories of fundamental NP-hard problems and learn standard techniques for designing and analyzing approximation algorithms. The problems to be addressed in the lectures 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 introduce classic approximation algorithms and state-of-the-art status for the above categories of problems. The lectures will be mostly technique-oriented with the algorithms being examples. Throughout this course, students will learn to design and analyze their own approximation algorithms.
Linear Algebra, Algorithms
Lectures
Homework: 40% Midterm: 30% Paper Reading & Group Presentation: 40%
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction on Approximation Algorithms and Problems to Address |
| 第 2 週 | Combinatorial-based Methods, O(log n)-approx for Set Cover, 2-approx for k-Center, 3-approx for Facility Location |
| 第 3 週 | FPTAS for Knapsack, Asymptotic PTAS for Bin Packing, PTAS for Identical Machine Scheduling |
| 第 4 週 | 3/2-approx for Metric TSP, PTAS for Euclidean TSP |
| 第 5 週 | O(log n)-approx of Metrics by Tree Metrics, Spanners* |
| 第 6 週 | LP-Based Methods, LP Relaxation as a Tool for Lower-bounding OPT, Design of LP relaxations, LP solvers |
| 第 7 週 | LP duality: theorem and further properties, Deterministic / Randomized Rounding, 2-approx for Vertex Cover, (1+2/e)-approx for Facility Location, 3/2-approx for Multiway Cut |
| 第 8 週 | Extreme Point Analysis of the Polytope, Half-Integrality of Vertex Cover, 2-approx for Unrelated Machine Scheduling |
| 第 9 週 | Dual-Fitting and Primal-Dual Schema, Reinterpretation of a Few Greedy Algorithms, 2-approx for Vertex Cover, 2-approx for Steiner Forest Problem |
| 第 10 週 | Iterative Rounding, 2-approx for Steiner Network, 2-approx for Capacitated Vertex Cover |
| 第 11 週 | Iterative Rounding, 2-approx for Steiner Network, 2-approx for Capacitated Vertex Cover |
| 第 12 週 | Factor-Revealing LP for Combinatorial-Based Methods, A 1.61-approx for Facility Location |
| 第 13 週 | MISC*, O(log k)-approx for Multi-Cut |
| 第 14 週 | 2-approx for Prize-Collecting Steiner Tree |
| 第 15 週 | Semi-definite Programming, 0.87856-approx for Max-Cut |
| 第 16 週 | Hardness of Approximation (if time permits) |
| 第 17 週 | |
| 第 18 週 |
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