Optimal Partitioning of Sequences

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 ƒ is minimized. An efficient algorithm which solves the problem in time O(( n − p) p log p) is deve...

Full description

Saved in:
Bibliographic Details
Published in:Journal of algorithms 1995-09, Vol.19 (2), p.235-249
Main Authors: Manne, F., Sorevik, T.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Classical combinatorial problems
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Mathematics
Sciences and techniques of general use
Theoretical computing
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ƒ is minimized. An efficient algorithm which solves the problem in time O(( n − p) p log p) is developed. The algorithm is based on finding a sequence of feasible nonoptimal 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.
ISSN:0196-6774
1090-2678
DOI:10.1006/jagm.1995.1035