{"id":"arxiv/2610.20140","url":"https://arxiv.org/abs/2610.20140","tags":["cs.DS","math.OC"],"score":0,"title":"An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint","domain":"cs.DS","source":"arxiv","authors":["Zizong Wang","Yibo Wang","Wenguo Yang"],"reviews":0,"subject":"cs.DS","summary":"We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone $k$-submodular function under a matroid constraint, for every $k\\ge2$. The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-14","reactions":{}}