  A deterministic approximation algorithm is presented for the maximization of
non-monotone submodular functions over a ground set of size $n$ subject to
cardinality constraint $k$; the algorithm is based upon the idea of interlacing
two greedy procedures. The algorithm uses interlaced, thresholded greedy
procedures to obtain tight ratio $1/4 - \epsilon$ in $O \left(
\frac{n}{\epsilon} \log \left( \frac{k}{\epsilon} \right) \right)$ queries of
the objective function, which improves upon both the ratio and the quadratic
time complexity of the previously fastest deterministic algorithm for this
problem. The algorithm is validated in the context of two applications of
non-monotone submodular maximization, on which it outperforms the fastest
deterministic and randomized algorithms in prior literature.
