Relaxations of linear programming formulations have been important tools for deriving heuristics with both good empirical and worst-case behavior. Non-linear relaxations may often give better results, but the tradeoff may be in tractability. Semi-definite programming (SDP) is an extension of linear programming that allows for efficient solution, both via polynomial-time methods for convex programming, like the ellipsoid method, and, more recently, various interior-point methods.
Semi-definite relaxations have recently made improvements to the approximation of various combinatorial problems whose solutions have long resisted attempt. We survey these developments and illustrate. This includes results of Goemans-Williamson for Max-Cut and Karger, Motwani, and Sudan for Graph Coloring. We also discuss indications of good heuristical behavior on problems in various domains, including clustering, and evolutionary trees.
Back to seminar homepage