3 papers
cs.DS2026
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…
cs.DS2026
Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard
Benjamin Moseley, Kirk Pruhs, Marc Uetz +1
This paper considers the scheduling of stochastic jobs on parallel identical machines to minimize the expected total weighted completion time. While this is a classical problem wit…
cs.DS2025
Robust Gittins for Stochastic Scheduling
Benjamin Moseley, Heather Newman, Kirk Pruhs +1
A common theme in stochastic optimization problems is that, theoretically, stochastic algorithms need to "know" relatively rich information about the underlying distributions. This…