Fast algorithms for k-submodular maximization subject to a matroid
  constraint
Shuxian Niu Qian Liu Yang Zhou Min Li
In this paper, we apply a Threshold-Decreasing Algorithm to maximize
$k$-submodular functions under a matroid constraint, which reduces the query
complexity of the algorithm compared to the greedy algorithm with little loss
in approximation ratio. We give a $(\frac{1}{2} - \epsilon)$-approximation
algorithm for monotone $k$-submodular function maximization, and a
$(\frac{1}{3} - \epsilon)$-approximation algorithm for non-monotone case, with
complexity $O(\frac{n(k\cdot EO + IO)}{\epsilon} \log \frac{r}{\epsilon})$,
where $r$ denotes the rank of the matroid, and $IO, EO$ denote the number of
oracles to evaluate whether a subset is an independent set and to compute the
function value of $f$, respectively. Since the constraint of total size can be
looked as a special matroid, called uniform matroid, then we present the fast
algorithm for maximizing $k$-submodular functions subject to a total size
constraint as corollaries. corollaries.