Refined Label Comparisons for Constrained Non-Monotone $k$-Submodular Maximization

Non-monotone $k$-submodular maximization under support constraints requires controlling both feasibility conflicts and label-dependent losses. We develop Random-root, a minimax randomized greedy method using support budgets, and a continuous algorithm that refines these comparisons through label-specific replacement losses. Under a matroid, the continuous algorithm improves the approximation coefficient from $\sqrt{2}-1$ to ${\alpha }_2\approx 0.4218$, up to any accuracy loss $\tau >0$. For every $k\ge 2$ and fixed accuracy, the baseline uses $O(nk\rho )$ value queries for $n$ elements and rank $\rho$. Refinements attain $0.4366-\tau$ for three to five labels and a uniform $0.4259-\tau$ guarantee for all $k\ge 3$. More generally, for orthant-submodular objectives with $r$-wise monotonicity, Random-root yields a closed-form approximation guarantee on $p$-systems, while continuous optimization attains ${\alpha }_r-\tau$ under matroid constraints, with ${\alpha }_r>1/(1+\sqrt{r})$ for $r\ge 2$. For $r\ge 3$, the extra-label refinement saturates at $k=r+1$: all $k>r$ share the same exact replacement-loss envelope.