A 1/2-Approximation for Budgeted $k$-Submodular Maximization

Chenhao Wang

A $k$-submodular function naturally generalizes submodular functions by taking as input $k$ disjoint subsets, rather than a single subset. Unlike standard submodular maximization,…