Max-sum diversity via convex programming

DOI10.4230/LIPICS.SOCG.2016.26zbMATH Open1387.68298arXiv1511.07077OpenAlexW2962988468MaRDI QIDQ3132860FDOQ3132860

Authors: Alfonso Cevallos, Friedrich Eisenbrand, Rico Zenklusen 

Publication date: 30 January 2018

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.

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

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

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)

Cited In (11)

• An Improved Analysis of Local Search for Max-Sum Diversification
• Title not available (Why is that?)
• Efficient Approximations for the Online Dispersion Problem
• \(t\)-linearization for the maximum diversity problem
• Local Search for Max-Sum Diversification
• Away from each other
• Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
• Selecting a subset of diverse points based on the squared Euclidean distance
• Max-min dispersion on a line
• Maximizing single attribute diversity in group selection
• Obtaining approximately optimal and diverse solutions via dispersion

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)