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.