Fast exact algorithms for the maximum diversity problem

The Maximum Diversity Problem (MDP) is a fundamental and challenging problem with numerous applications in data summarization, clustering, feature selection, and so on. In this paper, we propose two exact algorithms, FastMDP and FastSDR, to efficiently solve MDP. Although both algorithms follow the branch-and-bound paradigm, they use different techniques. FastMDP is purely combinatorial and incorporates three novel strategies called dynamic ordering, two-layer upper bounding, and fast bound computing. FastSDR is based on a new semidefinite relaxation formulation, which enables it to achieve excellent performance on certain instances. Experiments based on standard benchmarks MDPLIB show that our algorithms significantly outperform state-of-the-art MDP algorithms on all instances. This marks the first substantial improvement to exact algorithms for MDP in the past decade. We also conduct experiments to confirm the effectiveness of the novel strategies adopted by FastMDP.