A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio

We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines. By constructing competitive ratio approximation schemes we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also generalize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations.