4 citations · 5 across the 7 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
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…