Browsing by Author "Boros, E"

Now showing 1 - 1 of 1

Optimality of nested partitions and its application to cluster analysis
(1996-11-01)
Boros, E
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
A partition of a set N of n distinct numbers is called nested if four numbers a < b < c < d in N such that a and c are in one part while b and d in another do not exist. 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. In this paper we consider these notions in d-dimensional Euclidean spaces and 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, generalize some known results in this way, and propose some open problems.