Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


We consider the following general scheduling problem: There are $n$ jobs with arbitrary release times and sizes. In addition, each job has an associated arbitrary monotone function specifying the cost incurred when the job is completed at a particular time. This problem formulation is general enough to include many natural scheduling objectives, such as weighted flow time, weighted tardiness, and sum of flow time squared. The main contribution of this paper is a randomized polynomial-time algorithm with approximation ratio $O(log log (nP) )$, where $P$ is the maximum job size. This general result improves the best known approximation ratios by at least an exponential factor (and much more in some cases) for essentially {em all} of the nontrivial common special cases of this problem.

Our result is based on a novel connection between scheduling and geometry. We start with a certain strong linear programming relaxation for this problem, based on exponentially many knapsack cover inequalities. We show that the problem of rounding this linear program can be reduced to geometric weighted set multicover problems, where the sets/objects are have near linear union complexity. We then show how to apply Varadarajan's quasi-uniform sampling technique to obtain solutions for these geometric set multicover problems. We believe that this geometric interpretation of scheduling is of independent interest, and will likely find numerous future applications.

Questions and Answers

You need to be logged in to be able to post here.