210 citations · 283 across the 20 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.CG2011★ 1 cited
Approximating Low-Dimensional Coverage Problems
Ashwinkumar Badanidiyuru, Robert Kleinberg, Hooyeon Lee
We study the complexity of the maximum coverage problem, restricted to set systems of bounded VC-dimension. Our main result is a fixed-parameter tractable approximation scheme: an…
cs.GT2011★ 2 cited
Optimization with Demand Oracles
Ashwinkumar Badanidiyuru, Shahar Dobzinski, Sigal Oren
We study \emph{combinatorial procurement auctions}, where a buyer with a valuation function and budget wishes to buy a set of items. Each item has a cost and the…