22C:253 Algorithms in Discrete Optimization

9:30-10:20 MWF Room 205 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/231) left off, with NP-completeness and approximation algorithms. Given that many 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 problems, algorithms, and techniques that occupy an important place in the landscape of approximability. 22C:153/231 or an equivalent course taken elsewhere is a prerequisite.

Sources:

Approximation Algorithms by Vijay Vazirani, Springer-Verlag, Corrected Second Printing 2003, (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.

This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

If you have any complaints or concerns about how the course is being conducted by me or by the TAs please feel free to talk to me. You are also welcome to get in touch the the Computer Science department chair, Prof. Jim Cremer (cremer@cs.uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

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

Final exam: 14.7, 19.6, 23.4, 24.9, and one more problem here.

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 and Some Examples of Approximation Algorithms (5 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)

IP Formulations and Elementary LP Theory (3 lectures)

IP Formulations of Set Cover, Knapsack, Minimum Makespan
Different ways of writing an LP, Basic feasible solutions
A mention of the simplex method, the ellipsoid method and the interior point method
Integrality Gap, unimodularity, and half-integrality of Vertex Cover (14)

LP Rounding (8 lectures)

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

Primal-Dual Scheme (8 lectures)

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

Hardness of Approximation (5 lectures)

Arora and Lund, Chapter 10 from Hochbaum and Shapter 29 from Vazirani

Lecture Notes

Students in the fall 2002 offering of this course submitted scribe notes based on my lectures. I have collected these into a single file: postscript and pdf. The two books we will use for the course are quite good and these notes are definitely not meant as a substitute for the text. These merely reflect my organization of the topics and my emphasis on certain topics over others. I have edited the first 12 chapters of the notes for content and style; the remaining chapters have not been subjected to this yet. So use at your own risk! My thanks to students from 22C:253 from fall 2002 for making this happen.