Fast algorithms for k-submodular maximization subject to a matroid constraint
This work addresses optimization challenges in machine learning and combinatorial settings, offering faster algorithms for constrained k-submodular maximization, though it is incremental as it builds on existing methods with improved efficiency.
The paper tackles the problem of maximizing k-submodular functions under a matroid constraint by proposing a Threshold-Decreasing Algorithm that reduces query complexity with minimal loss in approximation ratio, achieving a (1/2 - ε)-approximation for monotone functions and a (1/3 - ε)-approximation for non-monotone cases with complexity O(n(k·EO + IO)/ε log(r/ε)).
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} - ε)$-approximation algorithm for monotone $k$-submodular function maximization, and a $(\frac{1}{3} - ε)$-approximation algorithm for non-monotone case, with complexity $O(\frac{n(k\cdot EO + IO)}ε \log \frac{r}ε)$, 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.