MIT Department of Electrical Engineering & Computer Science

E E C S

EECS Fall 1999 Catalogue Supplement

6.893 Approximability of Optimization Problems (H)

MW 2:30-4, 24-307
Prof. Madhu Sudan, NE43-307, x9680
Prerequisite: Permission of instructor
3-0-9

Introduction: Combinatorial optimization. Complexity theory; P, NP, NP-completeness. Approximability as a performance measure.

Approximation algorithms: Combinatorial inequalities. Fractional and semidefinite relaxations.

Complexity issues: Gap problems. Complexity classes for optimization. Descriptive complexity and approximability. Reductions between optimization problems. Gap-preserving reductions. Linear reductions. Gadget reductions.

Inapproximability: Constraint satisfaction problems. Proofs and optimization. Approximability and Probabilistically checkable proofs (PCPs). Parameters of interest. Constructions of PCPs. Hardness results.

URL of this page: http://www-eecs.mit.edu/AY99-00/fall-cat/6893.html
Editor: Mibsy Brooks | Created: Jun 31, 1998 | Modified: Aug 25, 1999
Related page: EECS Fall 1999 Catalogue Supplement
To MIT EECS home page | Your comments and inquiries are welcome.