Tight kernels for covering and hitting: Point hyperplane cover and polynomial point hitting set

Jean Daniel Boissonnat, Kunal Dutta, Arijit Ghosh, Sudeshna Kolay

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The Point Hyperplane Cover problem in ℝd takes as input a set of n points in ℝ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 ℝd takes as input a family F of D-degree polynomials from a vector space R in ℝd, and determines whether there is a set of at most k points in ℝd that hit all the polynomials in F. For both problems, we exhibit tight kernels where k is the parameter.

Original languageEnglish
Title of host publicationLATIN 2018: Theoretical Informatics
Subtitle of host publication13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings
EditorsM.A. Bender, M. Farach-Colton, M.A. Mosteiro
Place of PublicationDordrecht
PublisherSpringer
Pages187-200
Number of pages14
ISBN (Electronic)978-3-319-77404-6
ISBN (Print)978-3-319-77403-9
DOIs
Publication statusPublished - 1 Jan 2018
Event13th Latin American Theoretical INformatics Symposium (LATIN 2018) - Buenos Aires, Argentina
Duration: 16 Apr 201819 Apr 2018
Conference number: 13
http://latin2018.dc.uba.ar/

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Latin American Theoretical INformatics Symposium (LATIN 2018)
Abbreviated titleLATIN 2018
CountryArgentina
CityBuenos Aires
Period16/04/1819/04/18
Internet address

Fingerprint Dive into the research topics of 'Tight kernels for covering and hitting: Point hyperplane cover and polynomial point hitting set'. Together they form a unique fingerprint.

Cite this