40 citations · 242 across the 33 of their papers we have counts for
Showing 2012 · cs.DSShow all
2 papers · 2 filters
cs.DS2012
Online submodular welfare maximization: Greedy is optimal
Michael Kapralov, Ian Post, Jan Vondrak
We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless $NP = R…
cs.DS2012★ 3 cited
On the Hardness of Welfare Maximization in Combinatorial Auctions with Submodular Valuations
Shahar Dobzinski, Jan Vondrak
We present a new type of monotone submodular functions: \emph{multi-peak submodular functions}. Roughly speaking, given a family of sets $\cF$, we construct a monotone submodular f…