AVERAGE-CASE ANALYSIS OF GREEDY ALGORITHM S FOR OPTIMIZATION PROBLEMSON SET SYSTEMS

Authors
BLOT J DELAVEGA WF PASCHOS VT SAAD R
Citation
J. Blot et al., AVERAGE-CASE ANALYSIS OF GREEDY ALGORITHM S FOR OPTIMIZATION PROBLEMSON SET SYSTEMS, Comptes rendus de l'Academie des sciences. Serie 1, Mathematique, 321(6), 1995, pp. 805-808
Citations number
3
Categorie Soggetti
Mathematics, General",Mathematics
Journal title
Comptes rendus de l'Academie des sciences. Serie 1, Mathematique → ACNP
ISSN journal
07644442
Volume
321
Issue
6
Year of publication
1995
Pages
805 - 808
Database
ISI
SICI code
0764-4442(1995)321:6<805:AAOGAS>2.0.ZU;2-T
Abstract
We present a general setting for the asymptotic analysis of greedy alg orithms for several optimization problems defined on random set system s, when the size ground set-size set system ratio remains constants. T he set systems are generated via bipartite graphs and the approximatio n of the Markov chains are performed using ordinary differential equat ions.