Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order.

Nitish Korula, Vahab S. Mirrokni, Morteza Zadimoghaddam

Browse the full STOC paper archive.