5 papers
Bayesian Probing on Graphs
Anupam Gupta, Benjamin Moseley, Rudy Zhou
We introduce a stochastic probing problem with correlated items. In our model, which we call Bayesian Probing, the correlations are modeled by an underlying graph . Each vertex…
Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences
Samuel McCauley, Benjamin Moseley, Helia Niaparast +1
In this paper, we study the fundamental problem of finding a stable matching in two-sided matching markets. In the classic variant, it is assumed that both sides of the market subm…
Faster Global Minimum Cut with Predictions
Benjamin Moseley, Helia Niaparast, Karan Singh
Global minimum cut is a fundamental combinatorial optimization problem with wide-ranging applications. Often in practice, these problems are solved repeatedly on families of simila…
Incremental Approximate Single-Source Shortest Paths with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +2
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing inte…
Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs
Benjamin Moseley, Aidin Niaparast, R. Ravi
We study an online generalization of the classic Joint Replenishment Problem (JRP) that models the trade-off between ordering costs, holding costs, and backlog costs in supply chai…