Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization

We study nonnegative, non-monotone k-submodular maximization with k≥2 labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region Psubseteq[0,1]n, the diagonal level zeta(P)=maxt∈[0,1]:t bf 1 ∈ P ranges from zeta=0, which carries no geometric promise, to zeta=1, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For k≥3, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on k. Explicit parameter choices give a nondecreasing certified profile underlineαk(zeta), in closed form on all of [0,1] when k=2. At zeta=0 we certify 0.4456ldots for k=2 and 0.4541ldots for every k≥3, improving the recent √2-1 guarantee for one matroid or one knapsack, as well as the 1/3-type guarantees for a fixed number of budgets; at zeta=1 we certify 1/2 for k=2, (√17-3)/2 for k=3,4, and k/(2k-1) for k≥5, whose excess over 1/2 is of order 1/k rather than the previous 1/k2. Value-retaining rounding transfers these guarantees to matroid and knapsack constraints, and the same field yields O(√ T) approximate regret online under gradient or post-decision value feedback.