DYNAMIC-PROGRAMMING AND CONVEX CLUSTERING

Authors
BATAGELJ V KORENJAKCERNE S KLAVZAR S
Citation
V. Batagelj et al., DYNAMIC-PROGRAMMING AND CONVEX CLUSTERING, Algorithmica, 11(2), 1994, pp. 93-103
Citations number
11
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
11
Issue
2
Year of publication
1994
Pages
93 - 103
Database
ISI
SICI code
0178-4617(1994)11:2<93:DACC>2.0.ZU;2-0
Abstract
In this paper the notion of convexity of clusterings for the given ord ering of units is introduced. In the case when at least one (optimal) solution of the clustering problem is convex, dynamic programming lead s to a polynomial algorithm with complexity O(kn(3)). We prove that, f or several criterion functions, convex optimal clusterings exist when dissimilarity is pyramidal for a given ordering of units.