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

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

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

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

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

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