137 citations · 650 across the 48 of their papers we have counts for
3 papers · 1 filter
The Query-commit Problem
Marco Molinaro, R. Ravi
In the query-commit problem we are given a graph where edges have distinct probabilities of existing. It is possible to query the edges of the graph, and if the queried edge exists…
A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
Amitabh Basu, Robert Hildebrand, Matthias Köppe +1
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map w…
Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro +1
In the stochastic knapsack problem, we are given a knapsack of size B, and a set of jobs whose sizes and rewards are drawn from a known probability distribution. However, we know t…