# Fast algorithms for k-submodular maximization subject to a matroid constraint

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 26 Jul 2023.

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

- [Fast and Private Submodular and k-Submodular Functions Maximization with Matroid Constraints](https://mlsanity.com/paper/2006.15744/) (2020)
- [On maximizing a monotone k-submodular function subject to a matroid constraint](https://mlsanity.com/paper/1607.07957/) (2016)
- [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)
- [On maximizing a monotone k-submodular function under a knapsack constraint](https://mlsanity.com/paper/2105.15159/) (2021)
- [Maximizing approximately k-submodular functions](https://mlsanity.com/paper/2101.07157/) (2021)
- [Derandomization for k-submodular maximization](https://mlsanity.com/paper/1610.07729/) (2016)
- [Improved randomized algorithm for k-submodular function maximization](https://mlsanity.com/paper/1907.12942/) (2019)

## Abstract (arXiv)

In this paper, we apply a Threshold-Decreasing Algorithm to maximize k-submodular functions under a matroid constraint, which reduces the query complexity of the algorithm compared to the greedy algorithm with little loss in approximation ratio. We give a (frac12 - ε)-approximation algorithm for monotone k-submodular function maximization, and a (frac13 - ε)-approximation algorithm for non-monotone case, with complexity O(fracn(k· EO + IO)ε log fracrε), where r denotes the rank of the matroid, and IO, EO denote the number of oracles to evaluate whether a subset is an independent set and to compute the function value of f, respectively. Since the constraint of total size can be looked as a special matroid, called uniform matroid, then we present the fast algorithm for maximizing k-submodular functions subject to a total size constraint as corollaries. corollaries.