Average case analysis of a greedy algorithm for the minimum hitting set problem
Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid (1992), Average case analysis of a greedy algorithm for the minimum hitting set problem, in Simon, Imre, LATIN '92 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 6-10, 1992. Proceedings, Springer : Berlin, p. 130-138. http://dx.doi.org/ 10.1007/BFb0023824
Type
Communication / ConférenceDate
1992Conference title
1st Latin American Symposium on Theoretical Informatics (LATIN'92)Conference date
1992-04Conference city
Sao PauloConference country
BrésilBook title
LATIN '92 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 6-10, 1992. ProceedingsBook author
Simon, ImrePublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
583Published in
Berlin
ISBN
978-3-540-55284-0
Number of pages
545Pages
130-138
Publication identifier
Metadata
Show full item recordAbstract (EN)
Let 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.Subjects / Keywords
minimum hitting set problem; Greedy algorithmsRelated items
Showing items related by title and author.
-
Fernandez de la Vega, Wenceslas; Blot, Joël; Paschos, Vangelis; Saad, Rachid (1995) Article accepté pour publication ou publié
-
Blot, Joël; Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid (1995) Article accepté pour publication ou publié
-
Stafylopatis, Andreas; Paschos, Vangelis; Fernandez de la Vega, Wenceslas (1998) Article accepté pour publication ou publié
-
Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Stafylopatis, Andreas (1991) Communication / Conférence
-
Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper