# Maximizing k-Submodular Functions and Beyond

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Sep 2014.

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

- [Learning Compiler Pass Orders using Coreset and Normalized Value Prediction](https://mlsanity.com/paper/2301.05104/) (2023)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)
- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [Online and Streaming Algorithms for Constrained k-Submodular Maximization](https://mlsanity.com/paper/2305.16013/) (2023)
- [Fast algorithms for k-submodular maximization subject to a matroid constraint](https://mlsanity.com/paper/2307.13996/) (2023)

## Abstract (arXiv)

We consider the maximization problem in the value oracle model of functions defined on k-tuples of sets that are submodular in every orthant and r-wise monotone, where k≥ 2 and 1≤ r≤ k. We give an analysis of a deterministic greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+r). For r=k, we give an analysis of a randomised greedy algorithm that shows that any such function can be approximated to a factor of 1/(1+√k/2). In the case of k=r=2, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of 1/2. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that NPneq RP. Extending a result of Ando et al., we show that for any k≥ 3 submodularity in every orthant and pairwise monotonicity (i.e. r=2) precisely characterize k-submodular functions. Consequently, we obtain an approximation guarantee of 1/3 (and thus independent of k) for the maximization problem of k-submodular functions.