111-1 Introduction to Approximation Algorithms
Announcements.
[ HW3 ] is announced, due: 12/30 (Fri)
Please read the slides [12-LP Duality.pdf ] and the lecture note [ Note-8.pdf ], Section 2 - Farkas' Lemma.
Topics
Slides
Lecture Notes
W1 - 9/16
Introduction
Basic Concepts & Definitions,
The Max-3SAT Problem
W2 - 9/23
Approximate to any Desirable Degree
FPTAS for the Knapsack Problem,
Existence of FPTAS,
Existence of FPTAS,
The Bin Packing Problem
W3 - 9/30
The hardness of approximation & the gap-creating technique,
Asymptotic PTAS for the Bin Packing Problem
Asymptotic PTAS for the Bin Packing Problem
W4 - 10/7
Greedy towards Cost-Efficiency
The set cover problem and an Hn-approximation,
The vertex cover problem and an f-approximation.
The vertex cover problem and an f-approximation.
W6 - W11 - Group Presentation for Selected Book Chapters
W6 - 10/21
13:20 - 14:00 (presentation)
Vazi - 7, Shortest Superstring
曾理揚、林佳萱、許傅聲、陳泰源、呂朋澐
14:10 - 14:50 (presentation)
Vazi - 11, Euclidean TSP
陳冠傑、陳柏曄、湯希然、簡駿騏、安德勒 (Ryan)
15:00 - 15:40 (presentation)
WS - 10.2, MIS in Planar Graphs
吳庭安、路浩玄、廖廷偉、謝維庭、吳柏澄
W7 - 10/28
Parametric Search via Approximate-or-Refute
The k-Center Problem and a 2-approximation
15:20 - 16:00 (presentation)
WS - 2.6, 9.3, Minimum Degree Spanning Tree
陳永諭、張友維、于子緯、桑德雷
MST-based Algorithms
The Steiner Tree Problem,
Approximation Factor Preserving Reductions, and
MST-based approximations.
Approximation Factor Preserving Reductions, and
MST-based approximations.
The Traveling Salesman Problem (TSP)
W8 - 11/4
Introduction to LP-based Methods
The basic framework & simple rounding scheme
15:20 - 16:00 (presentation)
Vazi - 10, Minimum Makespan Scheduling
李駿逸、張書維、劉宇承、陳義瑄、陶榮台
W9 - 11/11
Extreme Point Structure of Linear Polytopes
Half-integrality of vertex cover,
Unrelated machine scheduling and a 2-approximation
Unrelated machine scheduling and a 2-approximation
15:20 - 16:00 (presentation)
WS - 11.2, Min-Cost Bounded-Degree Spanning Tree
林澤宇、曾昱仁、謝翊庭、賴柏叡、陳彥廷
W10 - 11/18
Linear Programming Duality
The Weak Duality Theorem,
Complementary Slackness,
Complementary Slackness,
Simple Dual-Fitting scheme
15:20 - 16:00 (presentation)
Vazi - 25, k-Median
劉凱文、沈克軒、劉仲恩、陳清海 (Nicholas)
-- The remaining slides & content are not finalized yet and are subject to change --
W11 - 11/25
Designing a Better LP Relaxation
The Multiway Cut Problem and a (2-2/k)-approximation,
Multi-commodity Flow
Multi-commodity Flow
12:20 - 13:00 (presentation)
WS - 4.4, 14.1, Prize-Collecting Steiner Tree
耿鈺展、張竣翔、石孟祐、倪子傑、李承翰
W12 - W15 - Group Presentation for Selected Papers
W12 - 12/2
Iterative Rounding Scheme
The Steiner network problem and a 2-approximation
15:20 - 16:10 - (paper presentation)
"A 1.5-Approximation for Path TSP", SODA 2018.
吳庭安、路浩玄、廖廷偉、謝維庭、吳柏澄
W13 - 12/9
Semidefinite Programming (SDP)
The max-cut problem and a 0.878-approximation
15:20 - 16:10 - (paper presentation)
"Exact and Approximation Algorithms
for Many-To-Many Point Matching in the Plane", ISAAC 2021.
李駿逸、張書維、劉宇承、陳義瑄、陶榮台
W14 - 12/16
13:20 - 14:10 - (paper presentation)
"Approximating longest spanning tree with neighborhoods", ISAAC 2021.
曾理揚、林佳萱、許傅聲、陳泰源、呂朋澐
14:20 - 15:10 - (paper presentation)
"An improved LP-based approximation for steiner tree", STOC 2010.
耿鈺展、張竣翔、石孟祐、倪子傑、李承翰
15:20 - 16:10 - (paper presentation)
"Graph balancing: a special case of scheduling unrelated parallel machines", SODA 2008.
陳永諭、張友維、于子緯
W15 - 12/23
13:20 - 14:10 - (paper presentation)
"First Fit bin packing: A tight analysis", STACS 2013.
陳冠傑、陳柏曄、湯希然、簡駿騏、安德勒 (Ryan)
14:20 - 15:10 - (paper presentation)
"A new greedy approach for facility location problems", STOC 2002.
劉凱文、沈克軒、劉仲恩、陳清海 (Nicholas)
15:20 - 16:10 - (paper presentation)
"The Santa Claus problem", STOC 2006.
林澤宇、曾昱仁、謝翊庭、賴柏叡、陳彥廷
W16 - 12/30
*** Final Exam ***
Hardness of Approximation
Hardness via NP-hard reduction,
The PCP theorem & The Unique Game Conjecture
The PCP theorem & The Unique Game Conjecture
Complementing the Weak-Spots via Linear Combinations
Probabilistic Combination of Algorithms
Supplement
Fundamental Theorem for Linear Inequalities,
Strong LP Duality
Strong LP Duality