Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/44188
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Gouveia, João | - |
dc.contributor.author | Pfeiffer, James | - |
dc.date.accessioned | 2017-10-26T15:17:24Z | - |
dc.date.issued | 2014 | - |
dc.identifier.uri | https://hdl.handle.net/10316/44188 | - |
dc.description.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. | por |
dc.language.iso | eng | por |
dc.publisher | Elsevier | por |
dc.relation | info:eu-repo/grantAgreement/FCT/COMPETE/132981/PT | por |
dc.rights | embargoedAccess | - |
dc.title | A semidefinite approach to the K_i-cover problem | por |
dc.type | article | - |
degois.publication.firstPage | 156 | por |
degois.publication.lastPage | 160 | por |
degois.publication.issue | 2 | por |
degois.publication.title | Operations Research Letters | por |
dc.relation.publisherversion | https://doi.org/10.1016/j.orl.2014.01.003 | por |
dc.peerreviewed | yes | por |
dc.identifier.doi | 10.1016/j.orl.2014.01.003 | por |
dc.identifier.doi | 10.1016/j.orl.2014.01.003 | - |
degois.publication.volume | 42 | por |
dc.date.embargo | 2019-10-26T15:17:24Z | - |
uc.controloAutoridade | Sim | - |
item.openairetype | article | - |
item.fulltext | Com Texto completo | - |
item.languageiso639-1 | en | - |
item.grantfulltext | open | - |
item.cerifentitytype | Publications | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
crisitem.author.researchunit | CMUC - Centre for Mathematics of the University of Coimbra | - |
crisitem.author.orcid | 0000-0001-8345-9754 | - |
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
495
checked on Jul 17, 2024
Download(s)
180
checked on Jul 17, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.