Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time
This work addresses optimization challenges in network applications by providing faster deterministic algorithms for submodular maximization, though it is incremental as it builds on existing methods with improved efficiency.
The paper tackles the problem of maximizing a non-monotone, non-negative submodular function under a matroid constraint, improving the deterministic approximation ratio to 1/4 with O(nr) time complexity and introducing TwinGreedyFast, which achieves a 1/4-ε ratio in nearly-linear O(n/ε log(r/ε)) time, outperforming prior deterministic and randomized algorithms in empirical evaluations.
We study the problem of maximizing a non-monotone, non-negative submodular function subject to a matroid constraint. The prior best-known deterministic approximation ratio for this problem is $\frac{1}{4}-ε$ under $\mathcal{O}(({n^4}/ε)\log n)$ time complexity. We show that this deterministic ratio can be improved to $\frac{1}{4}$ under $\mathcal{O}(nr)$ time complexity, and then present a more practical algorithm dubbed TwinGreedyFast which achieves $\frac{1}{4}-ε$ deterministic ratio in nearly-linear running time of $\mathcal{O}(\frac{n}ε\log\frac{r}ε)$. Our approach is based on a novel algorithmic framework of simultaneously constructing two candidate solution sets through greedy search, which enables us to get improved performance bounds by fully exploiting the properties of independence systems. As a byproduct of this framework, we also show that TwinGreedyFast achieves $\frac{1}{2p+2}-ε$ deterministic ratio under a $p$-set system constraint with the same time complexity. To showcase the practicality of our approach, we empirically evaluated the performance of TwinGreedyFast on two network applications, and observed that it outperforms the state-of-the-art deterministic and randomized algorithms with efficient implementations for our problem.