Many optimzation problems that we encounter in practice are NP-hard and unlikely to be efficiently solvable. This has given rise to the area of approximation algorithms where the goal is to obtain approximately optimal solutions in polynomial time. In this course, we will cover the basic techniques of approximation algorithms using combinatorial ideas as well as polyhedral techniques based on convex relaxations.
Office hour: By appointment in LSRC D203. Email the instructor at debmalya@cs.duke.edu
Greedy Algorithms
Local Search
Discretization
Linear and Semi-definite Programming
Rounding Techniques
The Primal-Dual method
Course website: https://sites.google.com/view/duke-compsci-632-fall-2024
Course pages on Canvas: Approximation Algorithms | COMPSCI 632.01.Fa24 (duke.edu)