Average case analysis of greedy algorithms for optimisation problems on set systems

Fernandez de la Vega, Wenceslas; Blot, Joël; Paschos, Vangelis; Saad, Rachid

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

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 diﬀé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