13 citations · 17 across the 6 of their papers we have counts for
9 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…
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…
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…
Online Demand Scheduling with Failovers
Konstantina Mellou, Marco Molinaro, Rudy Zhou
Motivated by cloud computing applications, we study the problem of how to optimally deploy new hardware subject to both power and robustness constraints. To model the situation obs…
Configuration Balancing for Stochastic Requests
Franziska Eberle, Anupam Gupta, Nicole Megow +2
The configuration balancing problem with stochastic requests generalizes many well-studied resource allocation problems such as load balancing and virtual circuit routing. In it, w…
Minimizing Completion Times for Stochastic Jobs via Batched Free Times
Anupam Gupta, Benjamin Moseley, Rudy Zhou
We study the classic problem of minimizing the expected total completion time of jobs on identical machines in the setting where the sizes of the jobs are stochastic. Specifica…
A Competitive Algorithm for Throughput Maximization on Identical Machines
Benjamin Moseley, Kirk Pruhs, Clifford Stein +1
This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on identical machines. The main resu…
Structural Iterative Rounding for Generalized -Median Problems
Anupam Gupta, Benjamin Moseley, Rudy Zhou
This paper considers approximation algorithms for generalized -median problems. This class of problems can be informally described as -median with a constant number of extra…
Fast Noise Removal for -Means Clustering
Sungjin Im, Mahshid Montazer Qaem, Benjamin Moseley +2
This paper considers -means clustering in the presence of noise. It is known that -means clustering is highly sensitive to noise, and thus noise should be removed to obtain a…