Coordinate Partitioning for Difficult Euclidean Max-Sum Diversity Problems
针对欧几里得最大和多样性问题随坐标数增加而变难的特点，利用Schoenberg变换将欧氏距离转化为平方距离，提出新的划分策略和全局收敛割平面算法，有效求解高维实例，并构造了一类新挑战实例。
Divide and Conquer: Solving the Euclidean Diversity Problem Through Coordinate Partitioning A common technique for solving difficult optimization problems is to break them into easier-to-manage pieces, yet it is rarely obvious how to do so. This is especially true for the Euclidean max-sum diversity problem, which becomes increasingly difficult as the number of coordinates grows despite the problem size remaining the same. In “Coordinate Partitioning for Difficult Euclidean Max-Sum Diversity Problems,” Spiers, Bui, and Loxton use an old result by Schoenberg to transform Euclidean distances into their squared counterparts, enabling a functional decomposition of the problem’s objective. The authors introduce novel partitioning strategies as well as a globally convergent cutting-plane algorithm, which can effectively solve high-dimension instances. They also present a new class of challenging instances characterized by locations on the surface of a hyperball.