AVERAGE-CASE ANALYSIS OF GREEDY ALGORITHMS FOR OPTIMIZATION PROBLEMS ON SET SYSTEMS

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 probabili ty 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 componen ts. 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 o f ordinary differential equations.