5 citations · 26 across the 18 of their papers we have counts for
Showing 2016 · cs.DSShow all
2 papers · 2 filters
cs.DS2016★ 1 cited
Combinatorial Prophet Inequalities
Aviad Rubinstein, Sahil Singla
We introduce a novel framework of Prophet Inequalities for combinatorial valuation functions. For a (non-monotone) submodular objective function over an arbitrary matroid feasibili…
cs.DS2016★ 4 cited
Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
Anupam Gupta, Viswanath Nagarajan, Sahil Singla
Suppose we are given a submodular function over a set of elements, and we want to maximize its value subject to certain constraints. Good approximation algorithms are known for…