# Maximizing approximately k-submodular functions

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 18 Jan 2021.

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

- [Guarantees for Greedy Maximization of Non-submodular Functions with Applications](https://mlsanity.com/paper/1703.02100/) (2017)
- [Submodular Optimization under Noise](https://mlsanity.com/paper/1601.03095/) (2016)
- [Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees](https://mlsanity.com/paper/1304.0730/) (2013)
- [Combinatorial Penalties: Which structures are preserved by convex relaxations?](https://mlsanity.com/paper/1710.06273/) (2017)
- [Maximizing k-Submodular Functions and Beyond](https://mlsanity.com/paper/1409.1399/) (2014)
- [Improved Approximation Algorithms for k-Submodular Function Maximization](https://mlsanity.com/paper/1502.07406/) (2015)

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

- [A Unified Approach to Submodular Maximization Under Noise](https://mlsanity.com/paper/2510.21128/) (2025)
- [Fast algorithms for k-submodular maximization subject to a matroid constraint](https://mlsanity.com/paper/2307.13996/) (2023)
- [Fairness in Monotone k-submodular Maximization: Algorithms and Applications](https://mlsanity.com/paper/2411.05318/) (2024)
- [Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem](https://mlsanity.com/paper/2511.00869/) (2025)

## Abstract (arXiv)

We introduce the problem of maximizing approximately k-submodular functions subject to size constraints. In this problem, one seeks to select k-disjoint subsets of a ground set with bounded total size or individual sizes, and maximum utility, given by a function that is "close" to being k-submodular. The problem finds applications in tasks such as sensor placement, where one wishes to install k types of sensors whose measurements are noisy, and influence maximization, where one seeks to advertise k topics to users of a social network whose level of influence is uncertain. To deal with the problem, we first provide two natural definitions for approximately k-submodular functions and establish a hierarchical relationship between them. Next, we show that simple greedy algorithms offer approximation guarantees for different types of size constraints. Last, we demonstrate experimentally that the greedy algorithms are effective in sensor placement and influence maximization problems.