Computing coverage kernels under restricted settings
Author
dc.contributor.author
Barbay, Jérémy
Author
dc.contributor.author
Pérez Lantero, Pablo
Author
dc.contributor.author
Rojas Ledesma, Javiel
Admission date
dc.date.accessioned
2020-05-15T14:10:50Z
Available date
dc.date.available
2020-05-15T14:10:50Z
Publication date
dc.date.issued
2020
Cita de ítem
dc.identifier.citation
Theoretical Computer Science 815(2020) 270–288
es_ES
Identifier
dc.identifier.other
10.1016/j.tcs.2020.01.021
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/174740
Abstract
dc.description.abstract
Given a set B of d-dimensional boxes (i.e., axis-aligned hyperrectangles), a minimum coverage kernel is a subset of B of minimum size covering the same region as B. Computing it is NP-hard, but as for many similar NP-hard problems (e.g., Box Cover, and Orthogonal Polygon Covering), the problem becomes solvable in polynomial time under restrictions on B. We show that computing minimum coverage kernels remains NP-hard even when restricting the graph induced by the input to a highly constrained class of graphs. Alternatively, we present two polynomial-time approximation algorithms for this problem: one deterministic with an approximation ratio within 0(logn), and one randomized with an improved approximation ratio within 0(lgOPT)(with high probability).
es_ES
Patrocinador
dc.description.sponsorship
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT), CONICYT FONDECYT: 1170366, 1160543.
DICYT Vicerrectoria de Investigacion, Desarrollo e Innovacion USACH (Chile): 041933PL.
Programa Regional STICAMSUD (Chile): 19-STIC-02, CONICYT-PCHA/Doctorado Nacional/2013-63130209.
ONICYT Fondecyt/Postdoctorado: 3190550.