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.


Published in:
Mathematics Of Operations Research, 44, 4, 1494-1509
Year:
Nov 01 2019
Publisher:
Catonsville, INFORMS
ISSN:
0364-765X
1526-5471
Keywords:
Laboratories:




 Record created 2019-11-20, last modified 2020-04-20


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)