In the recent years semidefinite programming has become a widely used tool for designing better efficient algorithms for approximating hard combinatorial optimization problems and, more generally, polynomial optimization problems, which deal with optimizing a polynomial objective function over a basic closed semialgebraic set. The underlying paradigm is that, while testing nonnegativity of a polynomial is a hard problem, one can test efficiently whether it can be written as a sum of squares of polynomials, using semidefinite programming. In this note we sketch some of the main mathematical tools that underlie this approach and illustrate its application to some graph problems dealing with maximum cuts, stable sets and graph coloring.
Additional Metadata
Keywords semidefinite programming, combinatorial optimization, polynomial optimization, positive polynomial, sum of squares
THEME Logistics (theme 3)
Publisher Wiskundig Genootschap
Journal Nieuw Archief voor Wiskunde
Project Semidefinite programming and combinatorial optimization
Citation
Laurent, M. (2008). Semidefinite Programming in Combinatorial and Polynomial Optimization. Nieuw Archief voor Wiskunde, 5(9), 256–265.