Title: The Geometry of Scheduling

Abstract: We consider the following general scheduling problem: There are n jobs, each with an arbitrary release time, size, and a monotone function specifying the cost incurred when the job is completed at a particular time. The objective is to find a preemptive schedule of minimum aggregate cost. This problem formulation is general enough to include many natural scheduling objectives, such as weighted flow, weighted tardiness, and sum of flow squared.

Our main result is a randomized polynomial-time algorithm with an approximation ratio O(log log nP), which substantially improves the previous results even for very special cases. The key insight is to relate this problem to certain natural geometric problems in 2d and 3d, and use recent techniques developed for these geometric problems. 

Joint work with Kirk Pruhs.