Abstract

In recent years semidefinite programming has been successfully applied in combinatorial optimization and design of algorithms. The flagship discoveries in this field are the Goemans-Williamson algorithm for MAXCUT, and Lovasz’s method for computing the Shannon capacity of a pentagon. This course is a short introduction to this field. This short course starts with a brief review of linear programming and its applications in combinatorial optimization. Then semidefinite programming is introduced and the algorithm of Goemans and Williamson is presented. Next the Lovasz theta function and its applications are reviewed. Finally implications of semidefinite programming for proving direct product theorems are discussed.



Information: