# Derandomization for k-submodular maximization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Oct 2016.

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

- [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)

Submodularity is one of the most important property of combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of k-submodular function is NP-hard, and approximation algorithms are studied. For monotone k-submodular function, [Iwata, Tanigawa, and Yoshida 2016] gave k/(2k-1)-approximation algorithm. In this paper, we give a deterministic algorithm by derandomizing that algorithm. Derandomization scheme is from [Buchbinder and Feldman 2016]. Our algorithm is k/(2k-1)-approximation and polynomial-time algorithm.