Duke University
COMPSCI 632
Approximation Algorithms
Fall 2024
Overview
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.
Course Staff
Instructor
Office hour: By appointment in LSRC D203. Email the instructor at debmalya@cs.duke.edu
Lectures
Mondays and Wednesdays at 1:25 - 2:40 pm in LSRC D106
Syllabus (tentative list)
Combinatorial Techniques in approximation algorithms
Greedy Algorithms
Local Search
Discretization
Convex Programming based approximation algorithms
Linear and Semi-definite Programming
Rounding Techniques
The Primal-Dual method
Useful Links
Course website: https://sites.google.com/view/duke-compsci-632-fall-2024
Course pages on Canvas: Approximation Algorithms | COMPSCI 632.01.Fa24 (duke.edu)