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

Abstract

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 $(\frac{1}{2}-\frac{1}{2e})\approx 0.316$-approximation algorithm that evaluates $f$ $O(n^4{k}^3)$ times, based on the result of Sviridenko (2004) on submodular knapsack maximization.

arXiv commentThis manuscript is published in Operations Research Letters, but there is an error in the proof of Theorem 1. We provide a corrigendum in the end of this manuscript