# Improved Approximation Algorithms for k-Submodular Function Maximization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2015.

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

- [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)
- [Fast algorithms for k-submodular maximization subject to a matroid constraint](https://mlsanity.com/paper/2307.13996/) (2023)
- [Robust Approximation Algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraint](https://mlsanity.com/paper/2309.12025/) (2023)
- [Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem](https://mlsanity.com/paper/2511.00869/) (2025)

## Abstract (arXiv)

This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max1/3, 1/(1+a)-approximation by Ward and vZivn'y~(SODA'14), where a=max1, √(k-1)/4. We also show that for monotone k-submodular functions there is a polynomial-time k/(2k-1)-approximation algorithm while for any varepsilon>0 a ((k+1)/2k+varepsilon)-approximation algorithm for maximizing monotone k-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.