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.