Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01669884
Contributor : Kunal Dutta <>
Submitted on : Thursday, December 21, 2017 - 7:09:25 AM
Last modification on : Tuesday, February 11, 2020 - 5:20:01 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01669884, version 1

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⟩

Share

Metrics

Record views

333

Files downloads

385