Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/44188
Título: | A semidefinite approach to the K_i-cover problem | Autor: | Gouveia, João Pfeiffer, James |
Data: | 2014 | Editora: | Elsevier | Projeto: | info:eu-repo/grantAgreement/FCT/COMPETE/132981/PT | Título da revista, periódico, livro ou evento: | Operations Research Letters | Volume: | 42 | Número: | 2 | Resumo: | 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 |
Direitos: | embargoedAccess |
Aparece nas coleções: | I&D CMUC - Artigos em Revistas Internacionais |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
KiCover.pdf | 279.74 kB | Adobe PDF | Ver/Abrir |
Visualizações de página 50
485
Visto em 30/abr/2024
Downloads
170
Visto em 30/abr/2024
Google ScholarTM
Verificar
Altmetric
Altmetric
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.