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:

Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2001 (textbook).
Approximation Algorithms for NP-hard Problems edited by Dorit S. Hochbaum, PWS Publishing Company, 1997.

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)

What is an approximation algorithm?
Examples of approximation algorithms:
- 2-approximation algorithms for Vertex Cover (14), Minimum Makespan (10)
- O(log n)-approximation algorithm for Set Cover (2)
- PTAS for Minimum Makespan (10)
- FPTAS for Knapsack (8)

Elementary LP Theory (1 lecture)

Different ways of writing an LP, Basic feasible solutions
A mention of the simplex method, the ellipsoid method and the interior point method

LP Rounding (6 lectures)

Randomized rounding for Set Cover (14)
Half-integrality of Vertex Cover (14)
Randomized rounding for MAX-SAT (16)
Scheduling of unrelated parallel machines (17)
Steiner network (23)
k-median (25)

Primal-Dual Scheme (6 lectures)

Introduction to LP duality (12)
Set Cover via primal-dual (15)
Steiner forest (22)
Facility location (24)

Semi-definite programming (4 lectures)

Introduction to SDP (26)
Max-Cut (26)
Graph coloring (Karger, Motwani, Sudan, Vol 45, No.2, JACM, 1998)

Hardness of Approximation (4 lectures)

Arora and Lund, Chapter 10 from Hochbaum

Monte Carlo Markov Chain method (6 lectures)

Jerrum and Sinclair, Chapter 12, Hochbaum

Grading

There are three components that will determine your grade.

Scribe Notes: 20% For each class one student will be responsible for taking down notes. This student will then type these notes up and send me a LaTeX file that I will process and post on the course page. Depending on how many students we end up with, each student will be responsible for 3-4 classes. Each student will have two days to type up the scribe notes and send them to me. We will figure out a schedule for scribe note-takers on the first day of classes.
Homeworks: 40% I will assign 3-4 problem sets, and you will have about 3 weeks for each problem set.
Final: 40% This will be a take-home exam, for which you will have 2-3 days.

Lecture Notes

Introduction to Approximation Algorithms: pdf, latex, 8/26
Set Cover: Greedy Algorithm: pdf, latex, 8/28
FPTAS for Knapsack: pdf, latex, 9/4.
PTAS for Minimum Makespan: pdf, latex, 9/9.
IP Formulation: pdf, latex, 9/11.
Elementary LP Theory: pdf, latex, 9/16.
Total Unimodularity and Half Integrality: pdf, latex, for 9/18.
Randomized Rounding: Set Cover: pdf, latex, for 9/23.
Randomized Rounding: MAX-SAT: pdf, latex, for 9/25.
Derandomization: MAX-SAT: pdf, latex, for 9/30.
Deterministic Rounding: Scheduling on Unrelated Parallel Machines: pdf, latex, for 10/2.
Capacitated Vertex Cover: pdf, latex, for 10/7.
Dependent Rounding for Capacitated Vertex Cover, pdf, latex, 10/9.
Elementary Theory of LP duality, pdf, latex, 10/14.
The Primal-Dual Schema for approximation algorithms, pdf, latex, 10/16.
Approximation of Set Cover via the primal-dual schema, pdf, latex, 10/21.
Steiner Forest via the primal-dual schema, pdf, latex, 10/23.
Steiner Forest continued, pdf, latex, 10/28.
Facility Location via the primal-dual schema, pdf, latex, 10/30.
Facility Location continued, pdf, latex, 11/4.
Max-Cut via Semidefinite Programming, pdf, latex, 11/6.

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

Homeworks and Exam

Homework 1: Due on 10/30. Problems 2.6, 8.1, 8.2, 10.1, 14.5, 14.7.

Homework 2: Due on 11/20. Problems 15.4, 16.7, 17.1, 17.3, 22.8, 22.11.

Final exam: Due back by 5 pm on Friday, 12/20.

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.