# On maximizing a monotone k-submodular function under a knapsack constraint

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2021.

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

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

We study the problem of maximizing a non-negative monotone k-submodular function f under a knapsack constraint, where a k-submodular function is a natural generalization of a submodular function to k dimensions. We present a deterministic (frac12-frac12e)≈ 0.316-approximation algorithm that evaluates f O(n4k3) times, based on the result of Sviridenko (2004) on submodular knapsack maximization.