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

Hitting Set
Point Sets
Hyperplane
Covering
Polynomials
Cover
kernel
Polynomial
Vector spaces
Hits
Vector space
Integer

Cite this

Boissonnat, J. D., Dutta, K., Ghosh, A., & Kolay, S. (2018). Tight kernels for covering and hitting: Point hyperplane cover and polynomial point hitting set. In M. A. Bender, M. Farach-Colton, & M. A. Mosteiro (Eds.), LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings (pp. 187-200). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS). Dordrecht: Springer. https://doi.org/10.1007/978-3-319-77404-6_15
Boissonnat, Jean Daniel ; Dutta, Kunal ; Ghosh, Arijit ; Kolay, Sudeshna. / Tight kernels for covering and hitting : Point hyperplane cover and polynomial point hitting set. LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. editor / M.A. Bender ; M. Farach-Colton ; M.A. Mosteiro. Dordrecht : Springer, 2018. pp. 187-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{e195dedd84504c26932e7bd6ef40d7b4,
title = "Tight kernels for covering and hitting: Point hyperplane cover and polynomial point hitting set",
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.",
author = "Boissonnat, {Jean Daniel} and Kunal Dutta and Arijit Ghosh and Sudeshna Kolay",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-319-77404-6_15",
language = "English",
isbn = "978-3-319-77403-9",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "187--200",
editor = "M.A. Bender and M. Farach-Colton and M.A. Mosteiro",
booktitle = "LATIN 2018: Theoretical Informatics",
address = "Germany",

}

Boissonnat, JD, Dutta, K, Ghosh, A & Kolay, S 2018, Tight kernels for covering and hitting: Point hyperplane cover and polynomial point hitting set. in MA Bender, M Farach-Colton & MA Mosteiro (eds), LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10807 LNCS, Springer, Dordrecht, pp. 187-200, 13th Latin American Theoretical INformatics Symposium (LATIN 2018), Buenos Aires, Argentina, 16/04/18. https://doi.org/10.1007/978-3-319-77404-6_15

Tight kernels for covering and hitting : Point hyperplane cover and polynomial point hitting set. / Boissonnat, Jean Daniel; Dutta, Kunal; Ghosh, Arijit; Kolay, Sudeshna.

LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. ed. / M.A. Bender; M. Farach-Colton; M.A. Mosteiro. Dordrecht : Springer, 2018. p. 187-200 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10807 LNCS).

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

TY - GEN

T1 - Tight kernels for covering and hitting

T2 - Point hyperplane cover and polynomial point hitting set

AU - Boissonnat, Jean Daniel

AU - Dutta, Kunal

AU - Ghosh, Arijit

AU - Kolay, Sudeshna

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045377208&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-77404-6_15

DO - 10.1007/978-3-319-77404-6_15

M3 - Conference contribution

AN - SCOPUS:85045377208

SN - 978-3-319-77403-9

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 187

EP - 200

BT - LATIN 2018: Theoretical Informatics

A2 - Bender, M.A.

A2 - Farach-Colton, M.

A2 - Mosteiro, M.A.

PB - Springer

CY - Dordrecht

ER -

Boissonnat JD, Dutta K, Ghosh A, Kolay S. Tight kernels for covering and hitting: Point hyperplane cover and polynomial point hitting set. In Bender MA, Farach-Colton M, Mosteiro MA, editors, LATIN 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings. Dordrecht: Springer. 2018. p. 187-200. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-77404-6_15