On the Approximability of Partial VC Dimension
Bazgan, Cristina; Foucaud, Florent; Sikora, Florian (2016), On the Approximability of Partial VC Dimension, in Chan, T-H. Hubert; Li, Minming; Wang, Lusheng, Combinatorial Optimization and Applications, Springer : Berlin, p. 92-106. 10.1007/978-3-319-48749-6_7
Type
Communication / ConférenceExternal document link
https://arxiv.org/abs/1609.05110v2Date
2016Conference title
10th International Conference, COCOA 2016Conference date
2016-12Conference city
Hong KongConference country
ChinaBook title
Combinatorial Optimization and ApplicationsBook author
Chan, T-H. Hubert; Li, Minming; Wang, LushengPublisher
Springer
Published in
Berlin
ISBN
978-3-319-48748-9
Number of pages
793Pages
92-106
Publication identifier
Metadata
Show full item recordAuthor(s)
Bazgan, CristinaLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Foucaud, Florent
Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes [LIMOS]
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We introduce the problem Partial VC Dimension that asks, given a hypergraph H=(X,E) and integers k and ℓ, whether one can select a set C⊆X of k vertices of H such that the set {e∩C,e∈E} of distinct hyperedge-intersections with C has size at least ℓ. The sets e∩C define equivalence classes over E. Partial VC Dimension is a generalization of VC Dimension, which corresponds to the case ℓ=2k, and of Distinguishing Transversal, which corresponds to the case ℓ=|E| (the latter is also known as Test Cover in the dual hypergraph). We also introduce the associated fixed-cardinality maximization problem Max Partial VC Dimension that aims at maximizing the number of equivalence classes induced by a solution set of k vertices. We study the approximation complexity of Max Partial VC Dimension on general hypergraphs and on more restricted instances, in particular, neighborhood hypergraphs of graphs.Subjects / Keywords
VC dimension; parameterized complexity; approximationRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Foucaud, Florent; Sikora, Florian (2019) Article accepté pour publication ou publié
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2013) Communication / Conférence
-
Bazgan, Cristina; Chopin, Morgan; Nichterlein, André; Sikora, Florian (2014) Article accepté pour publication ou publié
-
Foucaud, Florent; Gras, Benjamin; Perez, Anthony; Sikora, Florian (2020) Communication / Conférence
-
Foucaud, Florent; Gras, Benjamin; Perez, Anthony; Sikora, Florian (2020) Article accepté pour publication ou publié