Scheduling partially ordered jobs faster than 2^n

Details Scheduling partially ordered jobs faster than 2^n Scheduling partially ordered jobs faster than 2^n

2011-08-03

arxiv.org/abs/1108.0810v1

Computer Science

Data Structures and Algorithms

full version of a paper accepted for ESA'11

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Scheduling partially ordered jobs faster than 2^n does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Scheduling partially ordered jobs faster than 2^n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling partially ordered jobs faster than 2^n will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-663861