22C:253 Algorithms in Discrete Optimization

2:30-3:45 MW Room 113 MLH


Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: TBA

This course will start where the graduate algorithms course (22C:153) left off, with NP-completeness and approximation algorithms. Given that most natural computational problems seem to be NP-complete, devising efficient approximation algorithms has become the main focus of algorithms research in the past decade. In this course we will study important problems, algorithms, and techniques that occupy an important place in the landscape of approximability. 22C:153 or an equivalent course taken elsewhere is a prerequisite.

Sources:

I need to hear from anyone who has a disability, which may require some modification of seating, testing or other class requirements so that appropriate arrangements may be made. Please see me after class or during my office hours.

Topics, Grading Policy, Lecture Notes, Announcements, Homeworks and Exams, Online Resources


List of Topics

This is a tentative plan for what we will study in the course. The numbers after the topics refer to chapters in Approximation Algorithms by Vazirani. For a couple of the topics we will use the book Approximation Algorithms for NP-hard problems, edited by Hochbaum.

Introduction (2 lectures)

Elementary LP Theory (1 lecture)

LP Rounding (6 lectures)

Primal-Dual Scheme (6 lectures)

Semi-definite programming (4 lectures)

Hardness of Approximation (4 lectures)

Monte Carlo Markov Chain method (6 lectures)


Grading

There are three components that will determine your grade.

Lecture Notes

Notes below the horizontal rule have not been edited by me yet; so use them at your own risk.

Homeworks and Exam


Online Resources

Here is a small selection of online resources relevant to approximation algorithms for NP-complete problems. I will update this list as I find other resources.