Viswanath Nagarajan - Stochastic Load Balancing on Unrelated Machines

Explore a lecture on stochastic load balancing for unrelated machines, delivered by Viswanath Nagarajan at the Hausdorff Center for Mathematics. Delve into the first constant factor approximation algorithm for minimizing expected makespan in unrelated machine scheduling with stochastic job processing times. Examine the efficiently computable lower bound via an exponential-sized LP and its rounding technique. Follow the progression from the problem introduction to the analysis of the proposed algorithm, covering topics such as optimization under uncertainty, effective size for unrelated machines, LP relaxation, and the generalized assignment problem. Gain insights into this previously open problem, even for related machines, and understand its significance in combinatorial optimization.

Intro
Load Balancing Problem
Load Balancing (Formally)
Optimization under Uncertainty
Stochastic Load Balancing
Natural Approach for Stochastic Optimization
Deterministic Surrogate for Load Balancing?
Related Work: Deterministic Job Sizes
Related Work: Stochastic Job Sizes
Main Results
Further Complication
Effective Size: Unrelated Machines
Approach in Deterministic Setting
Our Approach in Stochastic Setting
Valid Inequalities
LP Relaxation
Algorithm Outline
Rounding Overview
Generalized Assignment Problem
Rounding Algorithm: Constructing GAP Instance
Analysis Outline