21-691
Topics in Optimization
Semidefinite Programming for Combinatorial Optimization

Instructor

Reha Tütüncü, WEH 7219, x8-2558, reha+@andrew.cmu.edu
Lectures: Monday-Wednesday 3:30-4:50pm WEH 6423
Office Hours: Monday 10:30am-12:00pm, Tuesday 2:30-4:00pm

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.

Homepage: http://www.math.cmu.edu/~reha/sdpco.html

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: