  


A Semidefinite Approach to the $K_i$ Cover Problem
Jo{\~a}o Gouveia (jgouveiamat.uc.pt) Abstract: We apply theta body relaxations to the $K_i$ cover problem and use this to show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all $K_i$$p$hole facets are valid, addressing an open question of Conforti et al \cite{conforti}. For the triangle free problem, we show for $K_n$ that the theta body relaxations do not converge by $(n2)/4$ steps; we also prove for all $G$ an integrality gap of 2 for the second theta body. Keywords: triangle free, theta body, semidefinite program, K_i cover Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF] Entry Submitted: 10/31/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  