550.770
MATH
SCIENCES:
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):
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.