Breaking the 1/3 Barrier for $\mathbf{k}$-Submodular Maximization under Matroid and Knapsack Constraints: A Proportional Top-2 Randomized Framework

Siyuan Chen, Shengminjie Chen, Suixiang Gao +3

$k$-submodularity generalizes submodularity by allowing each selected element to be assigned one of $k$ labels, rather than being merely selected or not selected. We study the prob…