A Combinatorial $(1/2-\epsilon )$-Approximation for $k$-Submodular Maximization under Multiple Knapsacks

Abstract

We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it samples from the two labels with the largest marginal gains, with probabilities proportional to the positive parts of these gains. Extending their single-knapsack Bellman analysis, we construct a common resource potential and associated resource weights, with potential losses charged to greedy gains. Since these weights depend on the unknown optimum, we discretize their defining coefficients and enumerate monotone guesses over phases determined by resource consumption. This yields an algorithm using at most $\mathcal{A}(d,\epsilon )(nk+1{)}^{H+2}$ value queries, where $n$ is the number of elements, $\mathcal{A}(d,\epsilon )$ depends only on $d$ and $\epsilon$, and $H=O(d\log (2d)/{\epsilon }^2)$. The approximation ratio can be made arbitrarily close to the optimal oracle threshold for \( k=2 \) and is asymptotically tight as \(k \to \infty\).

arXiv comment23 pages