Deterministic Approximation for Submodular Maximization over a Matroid
  in Nearly Linear Time
  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}-\epsilon$ under
$\mathcal{O}(({n^4}/{\epsilon})\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}-\epsilon$ deterministic ratio in
nearly-linear running time of
$\mathcal{O}(\frac{n}{\epsilon}\log\frac{r}{\epsilon})$. 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}-\epsilon$ 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.
