最大多样性精确算法

十年首次大幅提速

专为快速求解最大多样性问题设计的精确算法，采用动态排序与双层上界等新型策略，性能远超现有算法。

Jinping, Lei · Lu, Liu · 肖明宇 · Zhou, Yi

European Journal of Operational Research 2026

技术优势

全线提速

在标准 MDPLIB 基准集的全部实例上，新算法均能显著快于现有最优算法解决最大多样性问题。

十年首次

这是过去十年中，对最大多样性问题精确算法的第一次实质性改进。

双算法覆盖

FastMDP 基于纯组合技术，FastSDR 基于半定松弛，可在不同类型实例上发挥各自优势。

应用场景

• 数据摘要：从冗余数据中高效抽取代表性子集，加速摘要生成流程。
• 聚类分析：快速找到类间分散的质心，改善聚类结果的区分度。
• 特征选择：在特征空间中选择最大差异化子集，降低模型输入维度而不损失代表性。