Efficient partitioning of sequences

The authors consider the problem of partitioning a sequence of n real numbers into p intervals such that the cost of the most expensive interval, measured with a cost function f is minimized. This problem is of importance for the scheduling of jobs both in parallel and pipelined environments. The authors develop a straightforward and practical dynamic programming algorithm that solves this problem in time O(p(n-p)), which is an improvement of a factor of (logp) compared to the previous best algorithm. A number of variants of the problem are also considered.