A polynomial algorithm for balanced clustering via graph partitioning

DOI10.1016/J.EJOR.2020.07.031MaRDI QIDQ2029025zbMATH OpenOpenAlexFDO

Authors Nadine Kroher, L. E. Caraballo, J. M. Díaz-Báñez

Publication date 3 June 2021

Published in European Journal of Operational Research (Search for Journal in Brave)

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

zbMATH Keywords

clusteringdynamic programminggraph partitioning

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Abstract: The objective of clustering is to discover natural groups in datasets and to identify geometrical structures which might reside there, without assuming any prior knowledge on the characteristics of the data. The problem can be seen as detecting the inherent separations between groups of a given point set in a metric space governed by a similarity function. The pairwise similarities between all data objects form a weighted graph adjacency matrix which contains all necessary information for the clustering process, which can consequently be formulated as a graph partitioning problem. In this context, we propose a new cluster quality measure which uses the maximum spanning tree and allows us to compute the optimal clustering under the min-max principle in polynomial time. Our algorithm can be applied when a load-balanced clustering is required.

Recommendations

• Pairwise data clustering and applications
• EFFICIENT APPROXIMATION ALGORITHMS FOR PAIRWISE DATA CLUSTERING AND APPLICATIONS
• The weighted sum of split and diameter clustering
• Fast Clustering Algorithms
• An asymptotically exact polynomial algorithm for equipartition problems

Cites work

• A clustering algorithm for item assignment in a synchronized zone order picking system
• Cluster analysis and mathematical programming
• Efficient graph-based image segmentation
• Graph clustering
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Heuristics for the p-hub location problem
• scientific article; zbMATH DE number 3617544 (Why is no real title available?)
• Multiple heterogeneous unmanned aerial vehicles
• Optimum cut-based clustering

Cited in

(7)

• Improved algorithms for distributed balanced clustering
• Approximation algorithms for the maximally balanced connected graph tripartition problem
• Learning doubly stochastic and nearly idempotent affinity matrix for graph-based clustering
• Clustering with balancing constraints
• A New Greedy Algorithm for Improving b-Coloring Clustering
• Optimal hierarchical clustering on a graph
• Reconciling business analytics with graphically initialized subspace clustering for optimal nonlinear pricing

This page was built for publication: A polynomial algorithm for balanced clustering via graph partitioning

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