Text:None. We will be working with some classical and recent articles on the subject.
Work: Occasional HW problems, a half-hour in-class presentation on one of the articles we will cover.
Prerequisites: Some knowledge of combinatorial optimization and linear algebra of symmetric matrices. If in doubt come and talk to me about it.
This course will investigate the solution or approximation of certain combinatorial optimization problems through relaxations that involve positive semidefiniteness constraints. We will go over some of the classical results and then survey the recent developments in this field following the work of Goemans and Williamson on the maximum-cut problems. We will also focus on the computational issues and describe how the semidefinite relaxations are solved using interior-point methods.
The topics we will consider include: