# Max-Sum Diversification, Monotone Submodular Functions and Semi-metric Spaces

arXiv: https://arxiv.org/abs/1511.02402 · HTML: https://mlsanity.com/paper/1511.02402/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2015.

## Built on by (most cited first, 1 of 1)

- [Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees](https://mlsanity.com/paper/2110.09332/) (2021)

## Abstract (arXiv)

In many applications such as web-based search, document summarization, facility location and other applications, the results are preferable to be both representative and diversified subsets of documents. The goal of this study is to select a good "quality", bounded-size subset of a given set of items, while maintaining their diversity relative to a semi-metric distance function. This problem was first studied by Borodin et alciteborodin, but a crucial property used throughout their proof is the triangle inequality. In this modified proof, we want to relax the triangle inequality and relate the approximation ratio of max-sum diversification problem to the parameter of the relaxed triangle inequality in the normal form of the problem (i.e., a uniform matroid) and also in an arbitrary matroid.