Faster and Simpler Sketches of Valuation Functions

Keren Cohavi, Shahar Dobzinski

We present fast algorithms for sketching valuation functions. Let $N$ ($|N|=n$) be some ground set and $v:2^N\to \mathbb{R}$ be a function. We say that $\tilde v:2^N\rightar…