CSIC30148, F56 - ED102 - Introduction to Approximation Algorithms
Instructor - Prof. Mong-Jen Kao
Overview.
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 various 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, 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)
Course Evaluation.
Handwritten Homework (30%)
Midterm Exam (30%)
Book Chapter Report and Presentation (20%)
Paper Presentation (20%)
References.
Approximation Algorithms, by Vijay Vazirani, 2004.
The Design of Approximation Algorithms, by David Williamson and David Shmoys, 2012.