Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set

Abstract : The Point Hyperplane Cover problem in R d takes as input a set of n points in R d and a positive integer k. The objective is to cover all the given points with a set of at most k hyperplanes. The D-Polynomial Points Hitting Set (D-Polynomial Points HS) problem in R d takes as input a family F of D-degree polynomials from a vector space R in R d , and determines whether there is a set of at most k points in R d that hit all the polynomials in F. For both problems, we exhibit tight kernels where k is the parameter.
Type de document :
Communication dans un congrès
LATIN 2018 - 13th Latin American Theoretical INformatics Symposium, Apr 2018, Buenos Aires, Argentina
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01669884
Contributeur : Kunal Dutta <>
Soumis le : jeudi 21 décembre 2017 - 07:09:25
Dernière modification le : samedi 27 janvier 2018 - 01:31:23

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01669884, version 1

Collections

Citation

J.-D Boissonnat, Kunal Dutta, Arijit Ghosh, Sudeshna Kolay. Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set . LATIN 2018 - 13th Latin American Theoretical INformatics Symposium, Apr 2018, Buenos Aires, Argentina. 〈hal-01669884〉

Partager

Métriques

Consultations de la notice

166

Téléchargements de fichiers

52