Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/44188
Title: | A semidefinite approach to the K_i-cover problem | Authors: | Gouveia, João Pfeiffer, James |
Issue Date: | 2014 | Publisher: | Elsevier | Project: | info:eu-repo/grantAgreement/FCT/COMPETE/132981/PT | Serial title, monograph or event: | Operations Research Letters | Volume: | 42 | Issue: | 2 | 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, and study its relation to an open question of Conforti et al. 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. | URI: | https://hdl.handle.net/10316/44188 | DOI: | 10.1016/j.orl.2014.01.003 10.1016/j.orl.2014.01.003 |
Rights: | embargoedAccess |
Appears in Collections: | I&D CMUC - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
KiCover.pdf | 279.74 kB | Adobe PDF | View/Open |
Page view(s) 50
485
checked on Apr 16, 2024
Download(s)
167
checked on Apr 16, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.