| Article ID: | iaor1999889 |
| Country: | Netherlands |
| Volume: | 79 |
| Issue: | 1/3 |
| Start Page Number: | 143 |
| End Page Number: | 161 |
| Publication Date: | Oct 1997 |
| Journal: | Mathematical Programming |
| Authors: | Goemans Michel X. |
We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem.