Improving spectral bounds for clustering problems by Lagrangian relaxation

Clustering is one of the most important issues in data mining, image segmentation, VLSI design, parallel computing and many other areas. We consider the general problem of partitioning n points into k clusters by maximizing the affinity measure of the points into the clusters. This objective function, referred to as Ratio Association, generalizes the classical (Minimum) Sum-of-Squares clustering problem, where the affinity is measured as closeness in the Euclidean space. This generalized version has emerged in the context of the approximation of chemical conformations for molecules, and in explaining transportation phenomena in dynamical systems, especially in dynamical astronomy. In particular, we refer to the dynamical systems application in the paper. Although successful heuristics have been developed to approximately solve the problem, the conventional spectral bounds proposed in the literature are not tight enough for ‘‘large’’ instances to assert the quality of those heuristics or to allow solving the problem exactly. In this paper, we investigate how to tighten the spectral bounds by using Lagrangian relaxation and Subgradient optimization methods.