Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorFoucaud, Florent
dc.contributor.authorSikora, Florian
dc.date.accessioned2017-01-11T10:06:20Z
dc.date.available2017-01-11T10:06:20Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16147
dc.descriptionin Springer series Lecture Notes in Computer Science, vol. 10043en
dc.language.isoenen
dc.subjectVC dimensionen
dc.subjectparameterized complexityen
dc.subjectapproximationen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleOn the Approximability of Partial VC Dimensionen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages92-106en
dc.relation.ispartoftitleCombinatorial Optimization and Applicationsen
dc.relation.ispartofeditorChan, T-H. Hubert
dc.relation.ispartofeditorLi, Minming
dc.relation.ispartofeditorWang, Lusheng
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2016
dc.relation.ispartofpages793en
dc.relation.ispartofurl10.1007/978-3-319-48749-6en
dc.identifier.urlsitehttps://arxiv.org/abs/1609.05110v2
dc.contributor.countryeditoruniversityotherFRANCE
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-319-48748-9en
dc.relation.conftitle10th International Conference, COCOA 2016en
dc.relation.confdate2016-12
dc.relation.confcityHong Kongen
dc.relation.confcountryChinaen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-319-48749-6_7en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-11T09:56:49Z
hal.person.labIds989
hal.person.labIds857
hal.person.labIds989
hal.identifierhal-01431728*


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record