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

Debmalya Panigrahi

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)

Page updated

Google Sites

Report abuse