Group for Research in Decision Analysis

# Decremental clustering for the solution of $$p$$-dispersion problems to proven optimality

## Claudio Contardo

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