Fast exact algorithms for the maximum diversity problem

Jinping Lei, Lu Liu, Mingyu Xiao and Yi Zhou

European Journal of Operational Research, 2026, vol. 331, issue 2, 396-405

Abstract: 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.

Keywords: Combinatorial optimization; Branch and bound; Maixmum diversity problem; Semidefinite programming (search for similar items in EconPapers)
Date: 2026
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725009208
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:331:y:2026:i:2:p:396-405

DOI: 10.1016/j.ejor.2025.11.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().