On The Optimality of Nested Partitions

A partition of a set N of n distinct numbers is called nested if there do not exist four numbers a b c d in N such that a and c are in one part while b and d in another. A partition is called a p-partition if the number of parts is specified at p, and a shape-partition if the sizes of the p parts are also specified. There are exponentially many p-partitions but only polynomially many nested p-partitions. Recently, Boros and Hammer showed that under certain partition- cost functions, and optimal p-partition is always nested. In this paper we give a general condition on the cost structure for which an optimal shape-partition is always nested. We illustrate applications of our results to some clustering problems and propose some open problems.