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

Siyuan Chen, Suixiang Gao, Zheyu Jiang +1

We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constrain…