{"id":"arxiv/2610.04049","url":"https://arxiv.org/abs/2610.04049","tags":["cs.DS","cs.LG","math.OC"],"score":0,"title":"Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization","domain":"cs.DS","source":"arxiv","authors":["Vaneet Aggarwal"],"reviews":0,"subject":"cs.DS","summary":"We study nonnegative, non-monotone $k$-submodular maximization with $k\\ge2$ 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 $P\\subseteq[0,1]^n$, the diagonal level $ζ(P)=\\max\\{t\\in[0,1]:t {\\bf 1} \\in P\\}$ ranges from $ζ=0$, which carries no geometric promise, to $ζ=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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}