Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm

Motivated by sequential budgeted allocation problems, we investigate online matching problems where connections between vertices are not i.i.d., but they have fixed degree distributions - the so-called configuration model.