10 citations · 11 across the 3 of their papers we have counts for
Showing cs.DSShow 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.DS2010★ 10 cited
Is submodularity testable?
C. Seshadhri, Jan Vondrak
We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a…
cs.DS2010★ 1 cited
Submodular Maximization by Simulated Annealing
Shayan Oveis Gharan, Jan Vondrák
We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [FOCS'07] showed a 2/5-approximation f…