Group for Research in Decision Analysis

G-2019-22

Decremental clustering for the solution of \(p\)-dispersion problems to proven optimality

Given \(n\) points, a symmetric dissimilarity matrix \(D\) of dimensions \(n\times n\) and an integer \(p\geq 2\), the \(p\)-dispersion problem (pDP) consists in selecting a subset of exactly \(p\) points in such a way that the minimum dissimilarity between any pair of selected points is maximum. The pDP is \(NP\)-hard when \(p\) is an input of the problem. We propose a decremental clustering method to reduce the problem to the solution of a series of smaller pDPs until reaching proven optimality. The proposed method can handle problems orders of magnitude larger than the limits of the state-of-the-art solver for the pDP for small values of \(p\).

, 13 pages