Algorithms Seminar
Online Load Balancing on Related Machines
Speaker:  Debmalya Panigrahi

Date: 
Thursday, August 31, 2017 
Time: 
12:00pm  1:00pm 
Location: 
D344 LSRC, Duke 


Abstract
A classic problem in scheduling is to balance the load from arriving jobs on a set of machines with nonuniform speed. For this problem, the wellknown slowfit algorithm is constantcompetitive for the makespan or Linfinity norm, but no results were known for other norms. In this work, we give a constantcompetitive algorithm for this problem for every Lp norm. Unlike the slowfit algorithm that uses a simple greedy assignment rule, our algorithm first solves a convex relaxation of the problem using a gradient descent method, and then rounds the solution using a novel framework that we call machine smoothing. Our algorithmic ideas also generalize to the vector scheduling problem, where jobs have vector loads instead of scalar loads.
This is based on joint work with Sungjin Im, Nat Kell, and Maryam Shadloo.
Biography
Debmalya Panigrahi is an Assistant Professor of Computer Science at Duke University.