# Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 50 references that are in the map.
- First posted on arXiv 18 Oct 2021.

## Builds on (most cited first, 11 of 11)

- [Maximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms](https://mlsanity.com/paper/1711.07214/) (2017)
- [Pareto Optimization for Subset Selection with Dynamic Cost Constraints](https://mlsanity.com/paper/1811.07806/) (2018)
- [Evolutionary Bi-objective Optimization for the Dynamic Chance-Constrained Knapsack Problem Based on Tail Bound Objectives](https://mlsanity.com/paper/2002.06766/) (2020)
- [Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments](https://mlsanity.com/paper/1806.08547/) (2018)
- [A General Coreset-Based Approach to Diversity Maximization under Matroid Constraints](https://mlsanity.com/paper/2002.03175/) (2020)
- [Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints](https://mlsanity.com/paper/2012.08738/) (2020)
- [On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling](https://mlsanity.com/paper/1504.06363/) (2015)
- [Max-sum diversity via convex programming](https://mlsanity.com/paper/1511.07077/) (2015)
- [Distributed Maximization of Submodular plus Diversity Functions for Multi-label Feature Selection on Huge Datasets](https://mlsanity.com/paper/1903.08351/) (2019)
- [Multi-objective Evolutionary Algorithms are Still Good: Maximizing Monotone Approximately Submodular Minus Modular Functions](https://mlsanity.com/paper/1910.05492/) (2019)
- [Max-Sum Diversification, Monotone Submodular Functions and Semi-metric Spaces](https://mlsanity.com/paper/1511.02402/) (2015)

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

- [From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds](https://mlsanity.com/paper/2209.13974/) (2022)
- [It's Morphing Time: Unleashing the Potential of Multiple LLMs via Multi-objective Optimization](https://mlsanity.com/paper/2407.00487/) (2024)
- [Surrogate-Assisted Evolutionary Reinforcement Learning Based on Autoencoder and Hyperbolic Neural Network](https://mlsanity.com/paper/2505.19423/) (2025)
- [Can Evolutionary Clustering Have Theoretical Guarantees?](https://mlsanity.com/paper/2212.01771/) (2022)
- [Runtime Analysis of Evolutionary Algorithms for Multi-party Multi-objective Optimization](https://mlsanity.com/paper/2501.16336/) (2025)

## Abstract (arXiv)

Given a ground set of items, the result diversification problem aims to select a subset with high "quality" and "diversity" while satisfying some constraints. It arises in various real-world artificial intelligence applications, such as web-based search, document summarization and feature selection, and also has applications in other areas, e.g., computational geometry, databases, finance and operations research. Previous algorithms are mainly based on greedy or local search. In this paper, we propose to reformulate the result diversification problem as a bi-objective maximization problem, and solve it by a multi-objective evolutionary algorithm (EA), i.e., the GSEMO. We theoretically prove that the GSEMO can achieve the (asymptotically) optimal theoretical guarantees under both static and dynamic environments. For cardinality constraints, the GSEMO can achieve the optimal polynomial-time approximation ratio, 1/2. For more general matroid constraints, the GSEMO can achieve an asymptotically optimal polynomial-time approximation ratio, 1/2-ε/(4n), where ε>0 and n is the size of the ground set of items. Furthermore, when the objective function (i.e., a linear combination of quality and diversity) changes dynamically, the GSEMO can maintain this approximation ratio in polynomial running time, addressing the open question proposed by Borodin. This also theoretically shows the superiority of EAs over local search for solving dynamic optimization problems for the first time, and discloses the robustness of the mutation operator of EAs against dynamic changes. Experiments on the applications of web-based search, multi-label feature selection and document summarization show the superior performance of the GSEMO over the state-of-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments.