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.


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

Grading Policy

Plus/Minus grading will be used for the course. There will be 4 homeworks and a final exam. Each component will be worth 20% of your grade.


None yet.

Homeworks and Exams

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)

IP Formulations and Elementary LP Theory (3 lectures)

LP Rounding (8 lectures)

Primal-Dual Scheme (8 lectures)

Hardness of Approximation (5 lectures)

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.