Semidefinite Programming in Combinatorial and Polynomial Optimization
Nieuw Archief voor Wiskunde , Volume 5 - Issue 9 p. 256- 265
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.
|Keywords||semidefinite programming, combinatorial optimization, polynomial optimization, positive polynomial, sum of squares|
|THEME||Logistics (theme 3)|
|Journal||Nieuw Archief voor Wiskunde|
|Project||Semidefinite programming and combinatorial optimization|
Laurent, M. (2008). Semidefinite Programming in Combinatorial and Polynomial Optimization. Nieuw Archief voor Wiskunde, 5(9), 256–265.