2 papers
cs.DS2026
A Combinatorial -Approximation for -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…
cs.DS2026
Breaking the 1/3 Barrier for constrained -Submodular Maximization: A Proportional Top-2 Randomized Framework
Siyuan Chen, Shengminjie Chen, Suixiang Gao +3
-submodularity generalizes submodularity by allowing each selected element to be assigned one of labels. We study the maximization of a non-monotone -submodular function,…