12 citations · 55 across the 25 of their papers we have counts for
3 papers · 1 filter
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…
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…
How to morph planar graph drawings
Soroush Alamdari, Patrizio Angelini, Fidel Barrera-Cruz +10
Given an -vertex graph and two straight-line planar drawings of the graph that have the same faces and the same outer face, we show that there is a morph (i.e., a continuous tra…