Efficient Partitioning of Sequences


We 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. We 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 $\log p$ compared to the previous best algorithm. A number of variants of the problem are also considered.