Review for NeurIPS paper: Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time

Summary and Contributions: Contribution: The paper gives a new deterministic algorithm for maximizing a non-monotone submodular function subject to a matroid constraint. The algorithm achieves a 1/4 approximation and it has a running time of O(n r), where n is the size of the ground set and r is the rank of the matroid. Using known techniques, one can speed up the algorithm to nearly-linear at a small loss in the approximation. Comparison to previous work: Previously, there were two main approaches for obtaining deterministic algorithms for the problem. The first approach, due to Lee et al., uses local search and it obtains a 1/4 - eps approximation but the running time is a much larger polynomial (at least n 4).