Semidefinite programs and combinatorial optimization

This survey on semidefinite programming (SDP) emphasizes the connection between SDP and discrete optimization problems. <P> Two introductory sections recall the basics from linear algebra, matrix analysis, linear programming and polyhedral combinatorics. The stable set polytope serves as an illustration. Moreover, SDP duality and algorithmic issues are briefly touched. <P> A first highlight of the paper is a discussion of various methods and techniques that can be used to obtain SDP relaxations of discrete problems: orthogonal representations of graphs, quadratic problems in binary variables, spectral graph theory and some engineering applications. It is instructive to see that seemingly unrelated techniques often lead to the same SDP relaxation. This is again pointed out in the case of the stable set problem. The author also gives a nice application of SDP to the discrepancy problem in number theory. <P> As a second highlight, the author shows the strong potential of SDP to get approximation results for hard combinatorial optimization problems. The hyperplane rounding technique of Goemans and Williamson is discussed for both the max-cut and the satisfiability problem. Moreover, various approximation results based on the theta-function are presented, to approximate the chromatic number as well as the stability number of a graph. Using SDP one obtains some of the currently strongest approximation results for these problems. <P> The final section starts with a discussion of the rank of optimal solutions to SDP. The typical situation is that a solution of rank one would solve the underlying discrete problem, so the main question here is, how small could the rank possibly be at the optimum? Finally, the paper states 18 (open) problems related to rank, approximation algorithms, and constraint generation of integer problems for SDP. <P> This paper is an excellent introduction to SDP in the context of complexity theory, polynomial-time approximation algorithms and discrete optimization. Ninety-nine references, most of which are not older than 10 years, indicate that SDP in combination with combinatorial optimization is indeed a very dynamic area of research. <P> For the entire collection see <A HREF="/msnmain?fn=105&fmt=doc&r=1&pg1=CNO&s1=1952980&loc=fromrevtext">MR1952980 (2003g:05003)</A>.