Instructor

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:

• Introduction to semidefinite programming.
• The Shannon capacity of a graph, Lovasz' Theta function and extensions.
• Lift-and -project schemes.
• Max-cut problem, max k-cuts, binary quadratic programming.
• Graph partitioning problems.
• Solving semidefinite programming problems--Interior-point methods.
• Quadratic assignment problem.