James Pfeiffer; The K_i Cover Problem with Semidefinite Programming

February 12, 2013, 4:00pm
Padelford C-401
James Pfeiffer, Department of Mathematics, University of Washington
The K_i Cover Problem with Semidefinite Programming

Abstract: The K_i cover problem is a generalization of the stable set problem to avoid larger cliques. Motivated by the Lovasz theta relaxation of the stable set polytope, we apply the related theta body relaxation of an algebraic variety to the K_i cover polytope. We show that for certain families of facets, the approximation is exact. For the triangle free problem (i=3), we prove a slow convergence result, and a bound on the integrality gap. This is joint work with Joao Gouveia.

Leave a Reply

Your email address will not be published. Required fields are marked *