Algorithms and complexity of range clustering

DOI10.1002/NET.21854MaRDI QIDQ3120783zbMATH OpenOpenAlexWikidataFDO

Authors Dorit S. Hochbaum

Publication date 19 March 2019

Published in Networks (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.04984

zbMATH Keywords

clusteringcomplexityimage segmentationminimum cutpartitioningrange

Mathematics Subject Classification ID

Applications of graph theory (05C90) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Image analysis in multivariate analysis (62H35)

Abstract: We introduce a novel criterion in clustering that seeks clusters with limited range of values associated with each cluster's elements. In clustering or classification the objective is to partition a set of objects into subsets, called clusters or classes, consisting of similar objects so that different clusters are as dissimilar as possible. We propose a number of objective functions that employ the range of the clusters as part of the objective function. Several of the proposed objectives mimic objectives based on sums of similarities. These objective functions are motivated by image segmentation problems, where the diameter, or range of values associated with objects in each cluster, should be small. It is demonstrated that range-based problems are in general easier, in terms of their complexity, than the analogous similarity-sum problems. Several of the problems we present could therefore be viable alternatives to existing clustering problems which are NP-hard, offering the advantage of efficient algorithms.

Recommendations

• scientific article; zbMATH DE number 2081029
• scientific article; zbMATH DE number 3942814
• The weighted sum of split and diameter clustering
• An algorithm for minimizing clustering functions
• Clustering to minimize the maximum intercluster distance

Cited in

(5)

• On finding connected balanced partitions of trees
• Metaheuristics for the minimum gap graph partitioning problem
• Cardinality constrained connected balanced partitions of trees under different criteria
• scientific article; zbMATH DE number 5774596 (Why is no real title available?)
• Connected graph partitioning with aggregated and non‐aggregated gap objective functions

This page was built for publication: Algorithms and complexity of range clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3120783)