# Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jul 2023.

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

- [Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem](https://mlsanity.com/paper/2404.11496/) (2024)
- [Local Optima in Diversity Optimization: Non-trivial Offspring Population is Essential](https://mlsanity.com/paper/2407.08963/) (2024)

## Abstract (arXiv)

Finding diverse solutions to optimization problems has been of practical interest for several decades, and recently enjoyed increasing attention in research. While submodular optimization has been rigorously studied in many fields, its diverse solutions extension has not. In this study, we consider the most basic variants of submodular optimization, and propose two simple greedy algorithms, which are known to be effective at maximizing monotone submodular functions. These are equipped with parameters that control the trade-off between objective and diversity. Our theoretical contribution shows their approximation guarantees in both objective value and diversity, as functions of their respective parameters. Our experimental investigation with maximum vertex coverage instances demonstrates their empirical differences in terms of objective-diversity trade-offs.