# Sparsification of Monotone k-Submodular Functions of Low Curvature

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

## Key facts

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

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

- [Mini-batch Submodular Maximization](https://mlsanity.com/paper/2401.12478/) (2024)

## Abstract (arXiv)

Pioneered by Benczur and Karger for cuts in graphs [STOC'96], sparsification is a fundamental topic with wide-ranging applications that has been studied, e.g., for graphs and hypergraphs, in a combinatorial and a spectral setting, and with additive and multiplicate error bounds. Rafiey and Yoshida recently considered sparsification of decomposable submodular functions [AAAI'22]. We extend their work by presenting an efficient algorithm for a sparsifier for monotone k-submodular functions of low curvature.