An Improved Analysis of Local Search for Max-Sum Diversification

• 成果类型: Article
• 署名作者: Cevallos, Alfonso; Eisenbrand, Friedrich; Zenklusen, Rico
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2018.0982
• 发表日期: 2019
• 页码: 1494-1509
• 关键词: metric-spaces; submodular maximization; algorithms; approximation; dispersion; matroids

摘要

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.