Fast clustering algorithms

Fast clustering algorithms

0.00 Avg rating0 Votes
Article ID: iaor19982360
Country: United States
Volume: 6
Issue: 2
Start Page Number: 141
End Page Number: 154
Publication Date: Mar 1994
Journal: ORSA Journal On Computing
Authors: ,
Keywords: networks
Abstract:

This paper considers the problem of partitioning the vertices of a weighted complete graph into cliques of unbounded size and number, such that the sum of the edge weights of all cliques is maximized. The problem is known as the clique-partitioning problem and arises as a clustering problem in qualitative data analysis. A simple greedy algorithm is extended to an ejection chain heuristic leading to optimal solutions in all practical test problems known from literature. The heuristic is used to compute an initial lower bound as well as to guide branching in a branch and bound algorithm which is superior to present exact methods. Empirical data for all three algorithms are reported.

Reviews

Required fields are marked *. Your email address will not be published.