Title: 

Optimization under Uncertainty: Scheduling with Failover

Abstract: 

Modern decision-making pipelines almost always rely on ML/AI tools to quantify uncertainty via probability distributions. This naturally leads to stochastic models, which we would like to optimize over to drive better decisions. I will discuss my work in developing fundamental algorithmic techniques for stochastic combinatorial optimization to drive algorithm design in both theory and practice.

I will introduce a novel resource allocation problem arising in cloud data centers: demands arrive online and need to be assigned to devices subject to capacity constraints to maximize utilization. Further, to be robust against failure, our assignment must remain feasible even in failover scenarios – when some device fails. These novel failover constraints introduce new trade-offs not present in classic assignment problems.  We design asymptotically optimal online algorithms for this problem in both the worst- and average-case (where demands are drawn i.i.d. from an unknown distribution). Along the way, we will see a lesser-known probabilistic tool: stochastic monotone matchings. Preliminary experiments on real cloud workloads show the potential of our algorithms to generate more power-efficient allocations, which can save millions and significantly reduce the environmental impact of cloud computing.

Bio: 

Rudy is currently a postdoc at Carnegie Mellon, where he recently graduated with a PhD in the ACO (Algorithms, Combinatorics, and Optimization) program. He is broady interested in algorithm design - especially for discrete and stochastic optimization problems. His work draws on ideas from approximation algorithms, probability theory, and convex optimization to design improved algorithms and general-purpose technical tools for fundamental optimization problems. On the application side, he is interested in realizing the potential impact of theoretical algorithms in practice in areas such as data center scheduling and naval logistics.