# Approximation algorithms for k-submodular maximization subject to a knapsack constraint

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2023.

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

- [Stochastic k-Submodular Bandits with Full Bandit Feedback](https://mlsanity.com/paper/2412.10682/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of maximizing k-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a frac12(1-e-2)≈ 0.432 greedy approximation algorithm. For the non-monotone case, we are the first to consider the knapsack problem and provide a greedy-type combinatorial algorithm with approximation ratio frac13(1-e-3)≈ 0.317.