# Improved randomized algorithm for k-submodular function maximization

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

## Key facts

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

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

- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)
- [Fast algorithms for k-submodular maximization subject to a matroid constraint](https://mlsanity.com/paper/2307.13996/) (2023)

## Abstract (arXiv)

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata et al. gave randomized k/(2k-1)-approximation algorithm for monotone functions, and randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives frack2+12k2+1-approximation for k≥ 3. We also give a randomized frac√17-32-approximation algorithm for k=3. We use the same framework used in Iwata et al. and Ward and vZivn'y with different probabilities.