Local Search for Max-Sum Diversification

DOI10.1137/1.9781611974782.9MaRDI QIDQ4575743zbMATH OpenOpenAlexFDO

Authors Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.04557

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Abstract: We provide simple and fast polynomial time approximation schemes (PTASs) for several variants of the max-sum diversification problem which, in its most basic form, is as follows: Given n points p_1,...,p_n in R^d and an integer k, select k points such that the average Euclidean distance between these points is maximized. This problem commonly appears in information retrieval and web-search in order to select a diverse set of points from the input. In this context, it has recently received a lot of attention. We present new techniques to analyze natural local search algorithms. This leads to a (1-O(1/k))-approximation for distances of negative type, even subject to any matroid constraint of rank k, in time O(n k^2 log k), when assuming that distance evaluations and calls to the independence oracle are constant time. Negative type distances include as special cases Euclidean distances and many further natural distances. Our result easily transforms into a PTAS and improves on the only previously known PTAS for this setting, which relies on convex optimization techniques in an n-dimensional space and is impractical for large data sets. In contrast, our procedure has an (optimal) linear dependence on n. Using generalized exchange properties of matroid intersection, we show that a PTAS can be obtained for matroid intersection constraints as well. Moreover, our techniques, being based on local search, are conceptually simple and allow for various extensions. In particular, we get asymptotically optimal O(1)-approximations when combining the classic dispersion function with a monotone submodular objective, which is a very common class of functions to measure diversity and relevance. This result leverages recent advances on local search techniques based on proxy functions to obtain optimal approximations for monotone submodular function maximization subject to a matroid constraint.

Recommendations

• An improved analysis of local search for max-sum diversification
• Theory and Applications of Satisfiability Testing
• Max-sum diversity via convex programming
• scientific article; zbMATH DE number 1016966
• Diversification strategies in local search for a nonbifurcated network loading problem
• Local search for diversified top-\(k\) clique search problem
• Multi-directional local search
• On the deterministic complexity of searching local maxima

Cited in

(14)

• Maximization problems of balancing submodular relevance and supermodular diversity
• Provable randomized rounding for minimum-similarity diversification
• Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
• Dispersing and grouping points on planar segments
• Max-sum diversity via convex programming
• Max-sum diversification, monotone submodular functions, and dynamic updates
• Efficient approximations for the online dispersion problem
• Diversity maximization in doubling metrics
• An improved analysis of local search for max-sum diversification
• Max-min dispersion on a line
• Away from each other
• Obtaining approximately optimal and diverse solutions via dispersion
• Diverse data selection under fairness constraints
• Max-min four-dispersion problems

This page was built for publication: Local Search for Max-Sum Diversification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575743)