Abstract
A classical problem in scheduling is to optimize load balancing objectives in an online assignment of jobs to machines. If the machines have non-uniform speed, then the problem is called scheduling on related machines. In this talk, I will describe a new algorithm for this problem that achieves a constant-competitive assignment for any l-p norm objective. Previous to this work, a constant competitive ratio was known only for the makespan objective (l-infinity norm), via the well-known "slowest-fit" algorithm. Our new algorithm uses gradient descent to solve a convex relaxation of the problem, followed by a rounding technique based on a new framework called machine smoothing. In contrast, most previous relax-and-round algorithms for online problems have employed multiplicative weights to solve the convex relaxation, which incurs a super-constant loss in the competitive ratio. Our techniques also give new results for more general vector scheduling problems. This is joint work with Sungjin Im, Nat Kell, and Maryam Shadloo.