An Improved Analysis of Local Search for Max-Sum Diversification
Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen · Mathematics of Operations Research · 2019
We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set [Formula: see text] and an integer k, select k points in X so that the sum of all of their [Formula: see text] Euclidean distances is maximized. This problem has recently received a lot of attention in the context of information retrieval and web search. We focus on distances of negative type, a class that includes Euclidean distances of unbounded dimension, as well as several other natural distances, including nonmetric ones. We prove that local search over these distances provides simple and fast polynomial-time approximation schemes (PTASs) for variants that are constrained by a matroid or even a matroid intersection, and asymptotically optimal O(1)-approximations when combining the sum-of-distances objective with a monotone submodular function.