22C:253 Algorithms in Discrete Optimization
9:30-10:20 MWF Room 205 MLH
Sriram V. Pemmaraju
101G MLH, email@example.com, 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.
- 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
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 (firstname.lastname@example.org, 319-335-1713, 14D McLean Hall).
Consult the college policy on Student Complaints
Concerning Faculty Actions (online version)
for more information.
Homeworks and Exams,
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.
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
- Homework 1: Problems 2.6, 2.11, 8.1, 8.2, and 10.1. Posted Friday 9/10.
Due Friday 9/24.
- Final exam: 14.7, 19.6, 23.4, 24.9, and one more problem
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
- 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
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.