Optimal Partitioning of Sequences
Abstract
The problem of partitioning a sequence of $n$ real numbers into $p$ intervals
is considered. The goal is to find a partition such that the cost of the
most expensive interval measured with a cost function $f$ is minimized.
An efficient algorithm which solves the problem in time $O(p(n-p)\log p)$
is developed. The algorithm is based on finding a sequence of feasible
non-optimal partitions, each having only one way it can be improved to
get a better partition. Finally a number of related problems are considered
and shown to be solvable by slight modifications of our main algorithm.