Approximation Algorithms
FALL 1998

Instructor: Lenore Cowen, WH 202B, x7043, cowen@cs.jhu.edu
Office Hours: W 1:00--2:00, or by appointment.
Lectures: Wednesday 4-6pm, Thursday 12-1pm in Whitehead 304

Approximation algorithms have developed in response to the impossibility of solving a good many problems exactly. In the case of NP-Complete problems, we sacrifice optimality in favor of a ``good'' solution that can be computed efficiently. Trading-off optimality in favor of tractibility is the paradigm of approximation algorithms. Topics will include: approximate scheduling, graph partitioning methods, fractional relaxations, randomized algorithms, approximate counting, and approximate coloring.

Primary Text: Hochbaum, D., Approximation Algorithms for NP-Hard Problems.

Prerequisites: 550.666 or 600.463. 550.666 will be accepted as a co-requisite with permission of the instructor.

Scribe notes: Note: (each lecture represents 2 hours -- 3 lectures = 2 weeks of class):

  • Lecture 1 (Intro/Knapsack problem) 9/9ab
  • Lecture 2 (k-center problems) 9/10; 9/16a
  • Lecture 3 (set cover) 9/16b; 9/17
  • Lecture 4 (approximating shortest paths) 9/23ab
  • Lecture 5 (approximating shortest paths, part II) 9/24 9/30ab
  • Lecture 6 (the primal/dual method) 10/1 10/8
  • Guest Lecture by Samir Kuller 10/7ab
  • Lecture 7 (steiner forest) 10/14b, 10/15
  • Lecture 8 Guest Lecture by Leslie Hall 10/14a
  • Lecture 9 (Euclidian travelling salesman) 10/21ab 10/22
  • Lecture 10 (semidefinite methods: max cut and approx 3-coloring) 10/28ab 10/29
  • Lecture 11 (approx-isometric embeddings of metric spaces) 11/4ab
  • Lecture 12 Guest Lecture by Leslie Hall 11/11ab
  • Lecture 13 (approx multi-commodity flow) 11/5 11/12
  • No lecture 11/25 (Thanksgiving)
  • Lecture 14 (randomized methods for approximate counting) 11/18ab 11/19
  • Lecture 15 (bin packing) 12/2ab
  • Lecture 16 (conclusions and open problems)12/3

    Partial Bibliography: the following were used in preparation of lectures (will be extended and revised throughout the semester):
    Hochbaum's book, working notes from V. Vazarani, notes from forthcoming book of R. Motwani, Goemans' notes, papers of Dor-Halpern-Zwick, Cohen-Zwick, Awerbuch-Berger-Cowen-Peleg, journal version of Arora's TSP paper, Goemans-Williamson paper, Karger-Motwani-Sudan paper, notes of Williamson, Linial-London-Rabinovich, Leighton-Rao, Autmann-Rabani, papers of Jerrum-Sinclair, Sinclair-Jerrum, more to come.