Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization

Vaneet Aggarwal

We study the maximization of a nonnegative $k$-submodular function, not assumed monotone, in which each of $n$ elements receives one of $k\ge 2$ labels or stays unselected and the s…