難解計算問題專論
Selected Topics in Intractable Problems
| 節 | 週五 |
|---|---|
5 13:20–14:10 | 難解計算問題專論 ED102（光復） 2 節連堂 |
6 14:20–15:10 |
* 根據陽明交大上課時間表所列
This course aims to provide an in-depth introduction on fixed-parameter tractability (FPT) and a mild introduction on computational complexity theory with a focus on NP characterization and polynomial-time approximability. Course website: https://sites.google.com/nycu.edu.tw/111-2-int-problem-complexity
Linear Algebra, Probability, Algorithms, Formal Language
無備註
Lecture, prepared material, online material.
Topic study & presentation (book chapter / research paper): 60% Final exam: 40%
Parameterized Algorithms & Fixed-parameter Tractability
Introduction, Kernelization, Bounded Search Trees, Iterative Compression, Randomized Methods, Treewidth, Fixed-parameter intractability, The W-hierarchy
Hierarchies of integer programming relaxations
Lovasz-Schrijver Hierarchy, Sherali-Adams Hierarchy, The Lasserre Hierarchy
Hardness of Approximation
Interactive proof system, PCP theorem and hardness of approximation, Proof of PCP theorem (sketch), The unique game conjecture (UGC)
| 週次 | 主題 |
|---|---|
| 第 1 週 | *** Parameterized Algorithms & FPT *** Introduction 2023-02-17(五) |
| 第 2 週 | Kernelization, Bounded search trees 2023-02-24(五) |
| 第 3 週 | Iterative compression, Randomized methods 2023-03-03(五) |
| 第 4 週 | Treewidth and Tree decomposition 2023-03-10(五) |
| 第 5 週 | Fixed-parameter intractability, The W-hierarchy 2023-03-17(五) |
| 第 6 週 | Other topics (TBA) 2023-03-24(五) |
| 第 7 週 | (Tentative) *** Hierarchies of Integer Programming Relaxations *** Lovasz-Schrijver Hierarchy, Sherali-Adams Hierarchy 2023-03-31(五) |
| 第 8 週 | The Lasserre Hierarchy 2023-04-07(五) |
| 第 9 週 | *** NP Characterization & Hardness of Approximation *** Interactive proof system The PCP theorem and Characterization of NP 2023-04-14(五) |
| 第 10 週 | PCP theorem and Hardness of Approximation 2023-04-21(五) |
| 第 11 週 | The Unique Game Conjecture (UGC), Best algorithm & best lower-bound for the problems? 2023-04-28(五) |
| 第 12 週 | (Tentative) Proof of PCP theorem (sketch) 2023-05-05(五) |
| 第 13 週 | Final Exam 2023-05-12(五) |
| 第 14 週 | Group Presentation 2023-05-19(五) |
| 第 15 週 | Group Presentation 2023-05-26(五) |
| 第 16 週 | Group Presentation 2023-06-02(五) |
| 第 17 週 | 2023-06-09(五) |
| 第 18 週 | 2023-06-16(五) |
1. Parameterized algorithms, by Marek Cygan et al., 2016. 2. Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, 2009.
- 地點
- 教師未提供此項資料
- 時間
- 教師未提供此項資料
- 聯絡方式
- 教師未提供此項資料