Course Description
This is a graduate-level course on algorithms for finding approximate solutions to NP-complete problems. It introduces the class NP and explores the importance of the NP-complete problems. Approaches for finding approximate solutions to many combinatorial and LP-based problems will be discussed.
Athena Title
Approximation Algorithms
Prerequisite
CSCI 2670 or permission of department
Semester Course Offered
Not offered on a regular basis.
Grading System
A - F (Traditional)
Course Objectives
This course focuses on finding approximate solutions to NP-complete problems. At the end of the semester, all students should be able to do the following: 1. Define NP, weakly NP-complete and strongly NP-complete. 2. Understand the importance of the class of NP-complete problems and why there is a need for approximation algorithms for these problems. 3. Use reductions to prove a problem is NP-complete. 4. Argue whether the reduction proves the problem is NP- complete in the weak sense or in the strong sense. 5. Define polynomial time approximation scheme (PTAS) and fully polynomial time approximation scheme (FPTAS). 6. Develop and prove the correctness of a number of different approximation algorithms for combinatorial and LP-based algorithms.
Topical Outline
o Introduction to the class NP (~1.5 weeks) o Definition of P vs. NP, NP optimization problems and NP-completeness o Proving problems are (weakly/strongly) NP-complete through reductions from known NP-complete problems o Introduction to approximation algorithms via the vertex cover problem (~1-2 days) o Approximations for combinatorial algorithms (~6.5 weeks, 1-3 days per algorithm) o Set cover, Steiner tree and TSP, Multiway cut and k-cut, k-center, Feedback vertex set, Shortest superstring (time permitting), Knapsack, Bin packing, Minimum makespan scheduling and Eucilidean TSP (time permitting) o Approximations for LP-based algorithms (~6.5 weeks, 2-4 days per algorithm) o Introduction to LP-duality, Set cover via dual fitting, Rounding applied to set cover, Set cover via primal-dual schema, Maximum satisfiability, Scheduling on unrelated and parallel machines, Other selected topics as time permits