zbMATH — the first resource for mathematics

Semidefinite programming and integer programming. (English) Zbl 1194.90066
Aardal, K. (ed.) et al., Discrete optimization. Amsterdam: Elsevier (ISBN 0-444-51507-0/hbk). Handbooks in Operations Research and Management Science 12, 393-514 (2005).
Summary: This chapter surveys how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. The chapter begins with a general presentation of several methods for constructing hierarchies of linear and/or semidefinite relaxations for 0/1 problems. Then it moves to an in-depth study of two prominent combinatorial optimization problems: the maximum stable set problem and the max-cut problem. Details are given about the approximation of the stability number by the Lovász theta number and about the Goemans-Williamson approximation algorithm for max-cut, two results for which semidefinite programming plays an essential role, and we survey some extensions of these approximation results to several other hard combinatorial optimization problems.
For the entire collection see [Zbl 1103.90007].

90C22 Semidefinite programming
90C10 Integer programming