Average case analysis of a greedy algorithm for the minimum hitting set problem

Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid

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érence

Date

1992

Conference title

1st Latin American Symposium on Theoretical Informatics (LATIN'92)

Conference date

1992-04

Conference city

Sao Paulo

Conference country

Brésil

Book title

LATIN '92 1st Latin American Symposium on Theoretical Informatics, Sao Paulo, Brazil, April 6-10, 1992. Proceedings

Book author

Simon, Imre

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

583

Published in

Berlin

ISBN

978-3-540-55284-0

Number of pages

545

Pages

130-138

Abstract (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 algorithms