
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
Type
Article accepté pour publication ou publiéDate
1995Journal name
Theoretical Computer ScienceVolume
147Number
1-2Publisher
Elsevier
Pages
267-298
Publication identifier
Metadata
Show full item recordAbstract (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 problemRelated items
Showing items related by title and author.
-
Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Saad, Rachid (1992) Communication / Conférence
-
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é
-
Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper
-
Fernandez de la Vega, Wenceslas; Paschos, Vangelis; Stafylopatis, Andreas (1991) Communication / Conférence