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.