Model Releases
Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization
arXiv:2610.04049v1 Announce Type: cross Abstract: We study nonnegative, non-monotone k-submodular maximization with kge2 labels under support constraints, and show how the certified approximation coef
arXiv:2610.04049v1 Announce Type: cross Abstract: We study nonnegative, non-monotone k-submodular maximization with kge2 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)=max{tin[0,1]:t {f 1} in 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 kge3, 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 nderline{alpha}_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 kge3, improving the recent sqrt2-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, (sqrt{17}-3)/2 for k=3,4, and k/(2k-1) for kge5, whose excess over 1/2 is of order 1/k rather than the previous 1/k^2. Value-retaining rounding transfers these guarantees to matroid and knapsack constraints, and the same field yields O(sqrt T) approximate regret online under gradient or post-decision value feedback.
Related
Source: arXiv cs.LG | 2026-10-06