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
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
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.
- 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.
- 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.
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.