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


A classic problem in scheduling is to balance the load from arriving jobs on a set of machines with non-uniform speed. For this problem, the well-known slow-fit algorithm is constant-competitive for the makespan or L-infinity norm, but no results were known for other norms. In this work, we give a constant-competitive algorithm for this problem for every L-p norm. Unlike the slow-fit 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.


Debmalya Panigrahi is an Assistant Professor of Computer Science at Duke University.