Approximation algorithms for scheduling on unrelated machines

1. Recently, there were two talks on minimizing average flow time in this seminar: One by Ho-Leung Chan (Oct. 24th) on a lower bound for the online single machine problem, and one by Amit Kumar (Jun. 26th) on an algorithm for the offline unrelated machine problem. The latter algorithm gives on O(K)-approximation (where K is the number of different process times) using the single source unsplittable flow problem as a subroutine. I'll present an alternative algorithm that uses unweighted bipartite matching instead. (WAOA2008)

2. The problem of minimizing average job completion time can be approximated within an arbitrarily small constant in polynomial time for a large class of scheduling problems. (See the 11-authored paper by Afrati et al, FOCS 1999.) Somewhat surprisingly, the problem turns out to be APX-hard on unrelated machines. In this talk I will focus on how a simple modification of an algorithm by Skutella (JACM 2001) leads to an improved approximation ratio for minimizing average (weighted) completion time on unrelated machines. (ESA2008)