On maximizing a monotone k-submodular function under a knapsack constraint
Not on the map. Why?
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.
Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). First posted on arXiv 31 May 2021.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2023: 3; 2024: 1; 2025: 1.
5 papers.
- 2024Stochastic k-Submodular Bandits with Full Bandit Feedbackcited by 3
- 2023Online and Streaming Algorithms for Constrained k-Submodular Maximizationcited by 0
- 2023Fast algorithms for k-submodular maximization subject to a matroid constraintcited by 0
- 2023Robust Approximation Algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraintcited by 0
- 2025Fast Stochastic Greedy Algorithm for k-Submodular Cover Problemcited by 0
- 2025Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem2 Nov 2025
- 2024Stochastic k-Submodular Bandits with Full Bandit Feedback14 Dec 2024
- 2023Robust Approximation Algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraint21 Sep 2023
- 2023Fast algorithms for k-submodular maximization subject to a matroid constraint26 Jul 2023
- 2023Online and Streaming Algorithms for Constrained k-Submodular Maximization25 May 2023