๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal Partitioning of Sequences

โœ Scribed by F. Manne; T. Sorevik

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
621 KB
Volume
19
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

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((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. 1995 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

Optimal rectangular partitions
Optimal rectangular partitions
โœ Felipe C. Calheiros; Abilio Lucena; Cid C. de Souza ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 172 KB
Decision trees with optimal joint partit
Decision trees with optimal joint partitioning
โœ Djamel A. Zighed; Gilbert Ritschard; Walid Erray; Vasile-Marian Scuturici ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 544 KB

Decision tree methods generally suppose that the number of categories of the attribute to be predicted is fixed. Breiman et al., with their Twoing criterion in CART, considered gathering the categories of the predicted attribute into two supermodalities. In this article, we propose an extension of t

Optimality of consecutive and nested tre
Optimality of consecutive and nested tree partitions
โœ Chang, G. J.; Hwang, F. K. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 84 KB

We consider the problem of partitioning the vertex-set of a tree to p parts to minimize a cost function. Since the number of partitions is exponential in the number of vertices, it is helpful to identify small classes of partitions which also contain optimal partitions. Two such classes, called cons