4 papers · 1 filter
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…
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…