ملخص: 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 [infinity], 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.

لغة: إنجليزية