**Instructor:**
Samir Khuller Office: AVW 3369. Office phone: (301) 405--6765.
E-mail: samir@cs.umd.edu.

**Office Hours:** TuTh 11-12
If you cannot make these hours, please make an appointment to see
me at a different time.

**Ghodsi's Office Hours:** Tu 12:30--2:30, Thu 12:30--1:30 in AVW 1112.

*
I will update this page every week during the
semester. I will place all homeworks as well
as solutions to homeworks here. If you have any trouble
accessing them, please let me know. These are in postscript.
*

**Class Time:** Tu and Th 9:30--10:45am. CSI 3120.

**Course Overview:**
The main paradigm in the course will be the design and analysis of
algorithms for combinatorial optimization. We will cover problems that
can be solved optimally in polynomial time (matchings, flows, min-cost
flows) as well as study problems that are NP-hard, and for which we can develop
approximation algorithms.
I expect that the students are already familiar with
the material from CMSC 451 (minimum spanning trees, shortest paths, dynamic
programming, NP-completeness etc.). I will spend the first few weeks
covering some topics such as flows and matchings that you may or
may not be familiar with from an undergraduate algorithms course.

- Learning about efficient algorithms for basic problems that are used as building blocks elsewhere. These include matching, flow, min cost flows, primal-dual methods, LP-rounding etc.
- An understanding of the inherent complexity of problems: Polynomial time, NP-completeness, Approximation Algorithms etc. We will spend a large fraction of the semester studying techniques for designing approximation algorithms. Many of these involve fairly mathematical proofs.

*Approximation Algorithms*by Vijay Vazirani.-
*Approximation Algorithms for NP--hard problems*by Dorit Hochbaum (editor). -
*Combinatorial Optimization: Algorithms and Complexity*by Christos Papadimitriou and Ken Steiglitz.

**Course Work:**
Course work will consist of homeworks, and two exams on ** Oct 16 **
and ** Dec 6**. All exams
will be in class. Both exams will count as the MS Comp exam.

Do not forget to do the course evaluation!!!

**Grading:**
The relative weights of these
will be 20% for the homeworks, 40% for each exam.

**Homeworks:**

- Homework 1: Due Sep 6 (2007). Average:76
- Homework 2: Due Sep 18 (2007). Average: 77
- Homework 3: Due Oct 2 (2007). Average: 86!
- Homework 4: Due Oct 11 (2007). Average:80
- Homework 5: Due Oct 30. Average:87
- Homework 6: Due Nov 13. Average:85
- Homework 7: Due Nov 21 (by email to ghodsi@cs).
- Homework 8: Due Dec 4.

- Lecture 0: Course Overview. Optimization, discussion of easy and hard problems, graph coloring, map coloring, linear programming etc.
- Lecture 1: Matchings , Additional reading: Hopcroft-Karp Matching Algorithm
- Lecture 2: Two Processor Scheduling
- Lecture 3: Assignment Problem
- Lecture 4: Flows
- Lecture 5: More on Flows
- Lecture 6: Preflow-Push (CLRS)
- Lecture 7: Min Cost Flows
- Lecture 8: Min Mean Cycles
- Lecture 9: Min Mean Cycles (see handout)
- Lecture 10: NP-completeness of Vertex Cover (no notes)
- Lecture 11: Vertex Cover Approximation
- Lecture 12: Vertex Cover (Nemhauser Trotter)
- Lecture 13: EXAM 1 (CLOSED EVERYTHING) AVERAGE:67/
- Lecture 14: Set Cover
- Lecture 15: Steiner Trees/TSP (Read Chaps 1,2,3)
- Lecture 16: K-centers(see also Chap 5)
- Lecture 17: Scheduling (Chaps 10 and 17)
- Lecture 18: Paper also read Chap 4 (Cuts)
- Lecture 19: Chap 9 (Bin Packing)
- Lecture 20: Notes on LP (Read Chaps 12 and 13)
- Lecture 21: Primal Dual (Chap 22)
- Lecture 22: Primal Dual (proof)
- Lecture 23: Facility Location (Chap 24)
- Lecture 24: Facility Location by LP rounding (see Shmoys, Tardos, Aardal (STOC 1997)) Read pages 6 and 7 of our paper only
- Lecture 25: Guest Lecture by Bill Gasarch on hardness results for approximation
- Lecture 26: EXAM 2 9am-10:45am (2 standard 8.5x11 inch sheets allowed)