Scheduling partially ordered jobs faster than 2^n
Venue
ESA (2011) (to appear)
Publication Year
2011
Authors
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
BibTeX
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.
