• 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

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), Average case analysis of greedy algorithms for optimisation problems on set systems, Theoretical Computer Science, 147, 1-2, p. 267-298. http://dx.doi.org/10.1016/0304-3975(95)00242-O

View/Open
publi174.pdf (297.5Kb)
Type
Article accepté pour publication ou publié
Date
1995
Journal name
Theoretical Computer Science
Volume
147
Number
1-2
Publisher
Elsevier
Pages
267-298
Publication identifier
http://dx.doi.org/10.1016/0304-3975(95)00242-O
Metadata
Show full item record
Author(s)
Fernandez de la Vega, Wenceslas
Blot, Joël
Paschos, Vangelis
Saad, Rachid
Abstract (FR)
Nous présentons un cadre général pour l’analyse asymptotique d’algorithmes gloutons pour plusieurs problèmes d’optimisation sur des systèmes aléatoires d’ensembles lorsque le rapport entre la taille de l’ensemble de base et la taille du système d’ensembles reste constant. Les systèmes d’ensembles sont engendrés via des graphes biparties aléatoires et les approximations des chaînes de Markov sont réalisées à l’aide d’équations différentielles ordinaires.
Abstract (EN)
A general framework is presented for the asymptotic analysis of greedy algorithms for several optimisation problems such as hitting set, set cover, set packing, etc. applied on random set systems. The probability model used is specified by the size n of the ground set, the size m of the set system and the common distribution of each of its components. The asymptotic behaviour of each algorithm is studied when n and m tend to ∞, with m/n a fixed constant. The main tools used are the generation of random families of sets via random bipartite graphs and the approximation of Markov chains with small steps by solutions of ordinary differential equations.
Subjects / Keywords
hypergraph independent set; hitting set; set covering; average case approximation; polynomial time approximation algorithm; NP-complete problem

Related items

Showing items related by title and author.

  • Thumbnail
    Average case analysis of a greedy algorithm for the minimum hitting set problem 
    Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid (1992) Communication / Conférence
  • 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
    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
  • 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
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