40 citations · 242 across the 33 of their papers we have counts for
Showing 2012Show all
3 papers · 1 filter
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…
cs.GT2012★ 1 cited
The Computational Complexity of Truthfulness in Combinatorial Auctions
Shahar Dobzinski, Jan Vondrak
One of the fundamental questions of Algorithmic Mechanism Design is whether there exists an inherent clash between truthfulness and computational tractability: in particular, wheth…