Advanced Topics in Theory of Computing; Approximation Algorithms (CMSC 858E)

Class Time: TuTh 12:30pm - 1:45pm. CSI 2118.

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 two 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.
  • Semi-definite programming

Course Work:

  • Midterm: 30%
  • Final: 40%
  • Homework: 20% (one homework due every alternate week)
  • Team Project: 10%

Prerequisites: CMSC 451 (minimum spanning trees, shortest paths, dynamic programming, NP-completeness etc.).

Instructor: Samir Khuller

Office: AVW 3369. Office phone: (301) 405--6765.
samir@cs.umd.edu

Office Hours: Mon 2-4 p.m.. If you cannot make these hours, please make an appointment to see me at a different time.

Teaching Assistant: Sheng Yang

Office: AVW 3457.
styang@cs.umd.edu

Office Hours: Wed 2-4 p.m.. 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.

Readings

Main Textbook:

Further Reading:

Additional Useful Material:

Homeworks

  • Homework 1: link. Due date: 09/13, 5p.m.
  • Homework 2: link. Due date: 09/25, 5p.m.
  • Homework 3: link. Due date: 10/02, 5p.m.
  • Homework 4: link. Due date: 10/09, 5p.m.
  • Homework 5: same as midterm, details available on ELMS. Due date: 11/08, 5p.m.
  • Homework 6: link. Due date: 12/05, 5p.m.

Schedule

  • Lecture 1 (Aug 28): Overview
  • Lecture 2 (Aug 30): Vertex Cover
  • Lecture 3 (Sept 4): Linear Programming, LP Duality, Primal-Dual Method and its application
  • Lecture 4 (Sept 6): Nemhauser-Trotter, Set Cover and its log(n) hardness
  • Lecture 5 (Sept 11): Traveling Salsesperson Problem
  • Lecture 6 (Sept 13): Muffin problem by Prof. Bill Gasarch. Slides available on his homepage
  • Lecture 7 (Sept 18): K-center
  • Lecture 8 (Sept 20): scheduling on identicaly parallel machines (Sec 2.3).
  • Lecture 9 (Sept 25): scheduing on unrelated machines.
  • Lecture 10 (Sept 27): min degree spanning trees (Sec 2.6), submodular optimization (Sec 2.5).
  • Lecture 11 (Oct 2): knapsack problem (Sec 3.1), bin packing problem.
  • Lecture 12 (Oct 4): scheduling jobs on identical parallel machine (PTAS, Sec 3.2), continue on bin packing (Sec 3.3).
  • Lecture 13 (Oct 9): review for midterm.
  • Lecture 14 (Oct 11): in class midterm.
  • Lecture 15 (Oct 16): guest lecture by Prof. David Mount on PTAS of TSP.
  • Lecture 16 (Oct 18): Facility Location problem (Sec 4.5).
  • Lecture 17 (Oct 23): continue on Facility Location problem (Sec 4.5). Using Ellipsoid method (Sec 4.3).
  • Lecture 18 (Oct 25): scheduling, weighted completion time (Chapter 4). Prize-collecting Steiner Tree (Section 4.4).
  • Lecture 19 (Oct 30): randomized 3-approximation for the Facitility Location Problem (Section 5.8). 0.618-approximation for MAX SAT (Section 5.1-5.3).
  • Lecture 20 (Nov 1): 3/4-approximation for MAX SAT.
  • Lecture 21 (Nov 6): Primal-Dual method (Feedback Vertex Set, s-t shortest path problem, generalized steiner forest) (Section 7.1-7.4).
  • Lecture 22 (Nov 8): Continue on Primal-Dual method.
  • Nov 13: Canceled.
  • Lecture 23 (Nov 15): Uncapacitated facility location problem (Section 7.6)
  • Lecture 24 (Nov 20): Multiway Cut Problem (Section 8.1 and 8.2)
  • Nov 22: campus closed for Thanksgiving
  • Nov 27 and Nov 29: group presentations.
  • Lecture 25 (Dec 04): Multicut Problem (Section 8.3), briefly mentioned correlation clustering
  • Lecture 26 (Dec 06): Review

Project