ECE
ECE
ECE ECE


CSP Seminar

Stochastic load balancing on unrelated machines

Viswanath Nagarajan


Assistant Professor
University of Michigan Department of Industrial and Operations Engineering
 
Thursday, May 10, 2018
4:00pm - 5:00pm
1005 EECS

Add to Google Calendar

About the Event

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.

Biography

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).

Additional Information

Contact: Judi Jones

Phone: 763-8557

Email: asap@umich.edu

Sponsor(s): ECE

Faculty Sponsor: Dave Neuhoff

Open to: Public