Show simple item record

dc.contributor.authorFernandez de la Vega, Wenceslas
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorSaad, Rachid
dc.date.accessioned2011-03-22T09:39:28Z
dc.date.available2011-03-22T09:39:28Z
dc.date.issued1992
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5782
dc.language.isoenen
dc.subjectminimum hitting set problemen
dc.subjectGreedy algorithmsen
dc.subject.ddc003en
dc.titleAverage case analysis of a greedy algorithm for the minimum hitting set problemen
dc.typeCommunication / Conférence
dc.description.abstractenLet k be fixed. Let n and m denote integers and C = {C 1,...,C m} a family of m subsets drawn from an n-element set C. A subset H Í C is a hitting set for the family C if H has a non-empty intersection with each element of this family and the minimum hitting set problem is that of finding a hitting set of minimum cardinality. The purpose of this paper is to study the efficiency of a natural greedy algorithm for the approximate solution of the minimum hitting set problem when C is a random family of k-element subsets, k fixed, and when n and m tend to \tfracmnUnknown control sequence '\tfrac' = agr, a fixed constant.en
dc.identifier.citationpages130-138en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber583
dc.relation.ispartoftitleLATIN '92 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 6-10, 1992. Proceedingsen
dc.relation.ispartofeditorSimon, Imre
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate1992
dc.relation.ispartofpages545en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/BFb0023811en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-55284-0en
dc.relation.conftitle1st Latin American Symposium on Theoretical Informatics (LATIN'92)en
dc.relation.confdate1992-04
dc.relation.confcitySao Pauloen
dc.relation.confcountryBrésilen
dc.identifier.doihttp://dx.doi.org/ 10.1007/BFb0023824


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