# A Parameterized Family of Meta-Submodular Functions

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

## Key facts

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

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

- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)

## Abstract (arXiv)

Submodular function maximization has found a wealth of new applications in machine learning models during the past years. The related supermodular maximization models (submodular minimization) also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints. Hence, while there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems. We give a broad parameterized family of monotone functions which includes submodular functions and a class of supermodular functions containing diversity functions. Functions in this parameterized family are called γ-meta-submodular. We develop local search algorithms with approximation factors that depend only on the parameter γ. We show that the γ-meta-submodular families include well-known classes of functions such as meta-submodular functions (γ=0), metric diversity functions and proportionally submodular functions (both with γ=1), diversity functions based on negative-type distances or Jensen-Shannon divergence (both with γ=2), and σ-semi metric diversity functions (γ = σ).