Google Research

Scheduling partially ordered jobs faster than 2^n

ESA (2011) (to appear)

Abstract

In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. SCHED is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2^n n^O(1) time, and whether there exists an algorithms solving SCHED in O(c^n) time for some constant c < 2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work