Efficient Partitioning of Sequences
Abstract
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.
Back
to publication page