Optimization Online


A Semidefinite Approach to the $K_i$ Cover Problem

Jo{\~a}o Gouveia (jgouveia***at***mat.uc.pt)
James Pfeiffer (jpfeiff***at***math.washington.edu)

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 $(n-2)/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 (Semi-definite Programming )

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 10/31/2012
Entry Accepted: 10/31/2012
Entry Last Modified: 02/04/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society