Stochastic load balancing on unrelated machines

We consider the unrelated machine scheduling problem when job processing-times are stochastic. We provide the first constant factor approximation algorithm for the setting where one wants a fixed assignment of jobs to machines so as to minimize the expected makespan. The identical machines special case has been well-understood for several years, but the problem was previously open even in the case of related machines. Our main technical contribution is an efficiently computable lower bound via an exponential-sized linear program, and its rounding. This is joint work with A. Gupta, A. Kumar and X. Shen.
Viswanath Nagarajan is an Assistant Professor in the Department of Industrial and Operations Engineering, University of Michigan. From 2009-14 he was a Research Staff Member at IBM T.J. Watson Research Center. He has a Ph.D. in Algorithms, Combinatorics and Optimization from Carnegie Mellon University (2009) and a BTech in Computer Science from IIT Bombay (2003). Dr. Nagarajan's research interests are in combinatorial optimization and approximation algorithms. He has received the Gerald L. Thompson dissertation award at CMU (2009), a best paper award at the European Symposium on Algorithms (2010) and an NSF CAREER award (2018).