Applications of Semidefinite Programming in Combinatorial Optimization

Abstract

In this project we focus on the development of tools from Semidefinite Programming and Convex Analysis for applications in Combinatorial Optimization, aiming to generalize the approach from Polyhedral Combinatorics. We are interested on the facial structure of semidefinite relaxations for certain combinatorial problems and its correspondence with combinatorial properties of the problems at hand. As a byproduct, we hope to enhance our understanding about the real gain of semidefinite formulations that make them so tighter than linear formulations for certain problems, and potentially replicate this success in other problems.Most of the known results in this line of research revolves around the central object known as the theta body of a graph, from which one may define the Lovász theta function. The theory surrounding these objects is quite rich and elegant, and it also applies to the semidefinite program utilized by Goemans and Williamson in their famous approximation algorithm for the maximum cut problem. We describe certain research directions involving the facial structure of these objects and the corresponding optimality conditions, as well as broader avenues of research with the goal of determining the true power of semidefinite formulations in Combinatorial Optimization and otherwise.