%0 Journal Article
%T On the Greedy Algorithm for Combinatorial Auctions with a Random Order
%A Shahar Dobzinski
%A Ami Mor
%J Computer Science
%D 2015
%I arXiv
%X In this note we study the greedy algorithm for combinatorial auctions with submodular bidders. It is well known that this algorithm provides an approximation ratio of $2$ for every order of the items. We show that if the valuations are vertex cover functions and the order is random then the expected approximation ratio imrpoves to $\frac 7 4$.
%U http://arxiv.org/abs/1502.02178v1