Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142169 | Operations Research Letters | 2014 | 5 Pages |
Abstract
We apply theta body relaxations to the Ki-cover problem and show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all Ki-p-hole facets are valid, and study its relation to an open question of Conforti et al. For the triangle free problem, we show for Kn 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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
João Gouveia, James Pfeiffer,