The first part of the talk includes a fresh look at geometric representations of graphs as they relate to semidefinite optimization, its duality theory and combinatorial min-max theorems. In this first part, the SDPs are exact formulations of the underlying combinatorial problem.
The second part of the talk focuses on methods that attack more difficult problems. In particular, we consider two successive convex relaxation methods using polynomial valid inequalities and semidefinite optimization. We then analyze their performance on some combinatorial optimization problems. The first method is a strengthened version of the Sherali-Adams operator and the second one is a strengthened version of the Bienstock-Zuckerberg operator.
This talk is based on joint work with Yu-Hin Au and Marcel Silva.
Copyright. All Rights Reserved.