40 citations · 242 across the 33 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.DS2011★ 1 cited
Symmetry and approximability of submodular maximization problems
Jan Vondrak
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the v…
cs.GT2011★ 12 cited
An approximately truthful-in-expectation mechanism for combinatorial auctions using value queries
Shaddin Dughmi, Tim Roughgarden, Jan Vondrak +1
This manuscript presents an alternative implementation of the truthful-in-expectation mechanism of Dughmi, Roughgarden and Yan for combinatorial auctions with weighted-matroid-rank…
cs.DS2011
On Variants of the Matroid Secretary Problem
Shayan Oveis Gharan, Jan Vondrák
We present a number of positive and negative results for variants of the matroid secretary problem. Most notably, we design a constant-factor competitive algorithm for the "random…