**
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.