Max-sum diversity via convex programming

DOI10.4230/LIPICS.SOCG.2016.26MaRDI QIDQ3132860zbMATH OpenOpenAlexFDO

Authors Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen

Publication date 30 January 2018

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

zbMATH Keywords

approximation algorithmsconvex programmingembeddingsmatroidsgeometric dispersion

Mathematics Subject Classification ID

Convex programming (90C25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: Diversity maximization is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function $f(cdot)$ that measures diversity of a subset, the task is to select a feasible subset $S$ such that $f(S)$ is maximized. The emph{sum-dispersion} function $f(S)=su{m}_{x,yinS}d(x,y)$, which is the sum of the pairwise distances in $S$, is in this context a prominent diversification measure. The corresponding diversity maximization is the emph{max-sum} or emph{sum-sum diversification}. Many recent results deal with the design of constant-factor approximation algorithms of diversification problems involving sum-dispersion function under a matroid constraint. In this paper, we present a PTAS for the max-sum diversification problem under a matroid constraint for distances $d(cdot,cdot)$ of emph{negative type}. Distances of negative type are, for example, metric distances stemming from the $el{l}_2$ and $el{l}_1$ norm, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search.

Recommendations

• Local Search for Max-Sum Diversification
• An improved analysis of local search for max-sum diversification
• Max-sum diversification, monotone submodular functions, and dynamic updates
• Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
• Maximum diversity problem with squared Euclidean distance

Cited in

(13)

• Selecting a subset of diverse points based on the squared Euclidean distance
• Away from each other
• Max-sum diversification, monotone submodular functions, and dynamic updates
• \(t\)-linearization for the maximum diversity problem
• Provable randomized rounding for minimum-similarity diversification
• Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
• Local Search for Max-Sum Diversification
• scientific article; zbMATH DE number 7561387 (Why is no real title available?)
• An improved analysis of local search for max-sum diversification
• Maximizing single attribute diversity in group selection
• Obtaining approximately optimal and diverse solutions via dispersion
• Efficient approximations for the online dispersion problem
• Max-min dispersion on a line

This page was built for publication: Max-sum diversity via convex programming

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