• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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é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
Publication identifier
http://dx.doi.org/ 10.1007/BFb0023824
Metadata
Show full item record
Author(s)
Fernandez de la Vega, Wenceslas
Paschos, Vangelis
Saad, Rachid
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

Related items

Showing items related by title and author.

  • Thumbnail
    Average case analysis of greedy algorithms for optimisation problems on set systems 
    Fernandez de la Vega, Wenceslas; Blot, Joël; Paschos, Vangelis; Saad, Rachid (1995) Article accepté pour publication ou publié
  • Thumbnail
    Analyse en moyenne de la performance des algorithmes gloutons pour des problèmes d'optimisation sur des systèmes d'ensembles 
    Blot, Joël; Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid (1995) Article accepté pour publication ou publié
  • Thumbnail
    Average-case complexity for the execution of recursive definitions on relational databases 
    Stafylopatis, Andreas; Paschos, Vangelis; Fernandez de la Vega, Wenceslas (1998) Article accepté pour publication ou publié
  • Thumbnail
    On the mean execution time of recursive definitions on relational databases 
    Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Stafylopatis, Andreas (1991) Communication / Conférence
  • Thumbnail
    Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model 
    Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo