An Improved Analysis of Local Search for Max-Sum Diversification

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 X subset of R-d and an integer k, select k points in X so that the sum of all of their ((k)(2) ) 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.