An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint

Zizong Wang, Yibo Wang, Wenguo Yang

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\ge 2$. The algor…