Home Page for CMSC 858Y (Topics in Algorithms: Combinatorial Optimization: Algorithms and Complexity)
Instructor:
Samir Khuller Office: AVW 3369. Office phone: (301) 405--6765.
E-mail: samir@cs.umd.edu.
Office Hours: Mon 11-12.
If you cannot make these hours, please make an appointment to see
me at a different time.
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: Mon and Wed 3:30--4:45pm. CSIC 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.
Goals:
- 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.
Texts:
- 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.
Approximation
Compendium .
Course Work:
Course work will consist of a few ungraded homeworks
(answers will be discussed in class), and two in class exams.
The combined grade from both exams will count as the MS Comp exam.
Exam 2 will be from 3:30--5:00 in class on Mon, May 3
Do not forget to do the
course evaluation!!!
Grading:
The relative weights of these will be 50% for each exam.
Class Handout
Homeworks:
LIST OF LECTURES
- Lecture 1 (Jan 25): Course Overview. Optimization, discussion of easy and hard problems.
- Lecture 2: Matchings , Additional reading:
Hopcroft-Karp Matching Algorithm
- Lecture 3 (Feb 1): Assignment Problem
- Lecture 4: Two Processor Scheduling
- Lecture X: (Feb 8): I am giving a CS Colloq. in CSIC 1115 from 4-5 (SNOW DAY!)
- Lecture X: SNOW DAY!
- Lecture 5: (Feb 15) TSP via Christofides and other simple approximations
- Lecture 6: Guest lecture by Dave Mount on TSP Approximations for Euiclidean instances.
- Lecture 7: (Feb 22) Set Cover
- Lecture 8: K-centers
- Lecture 9: (Mar 1) Dept. Colloq. in CSIC 1115
- Lecture 10: Vertex Cover Approximation
- Lecture 11: (Mar 8) Review for Exam
- Lecture 12: (Mar 10) MIDTERM
- Lecture 13: (Mar 22) Bin Packing Approximation
- Lecture 14: FPTAS for Knapsack and discussion of Scheduling (see Chap. 10
in Vazirani book)
- Lecture 15: (Mar 29) Linear Programming
- Lecture 16: Nemhauser-Trotter Thm
- Lecture 17: (Apr 5) Primal Dual Method
(Chap 22)
- Lecture 18: Primal Dual Method (Chap 22)
- Lecture 19: (Apr 12)
Primal Dual Formal Proofs (see prev. lecture notes)
- Lecture 20: Primal Dual Method applied to Facility Location (see Chap 24
in Vazirani book, or paper by Jain and Vazirani (JACM 2001))
- Lecture 21: (Apr 19)
Facility Location by LP rounding
- Lecture 22: Scheduling on unrelated parallel machines (see Chap 17)
in Vazirani book
- Lecture 23: (Apr 26) Generalized Assignment Problem and
Set Cover by randomized rounding
- Lecture 24: Review of HW problems
- Lecture 25: (May 3) EXAM 2
- Lecture 26:Guest Lecture by Bill Gasarch on hardness results for approximation
- Lecture 27:Guest Lecture by Saeed Alaei on SDP for MAX CUT.