An adaptive algorithm for maximization of non-submodular function with a matroid constraint

In the paper, we design an adaptive algorithm for non-submodular set function maximization over a single matroid constraint. We measure the deviation of the set function from fully submodular with the help of the generic submodularity ratio \begin{document}$ \gamma $\end{document} . The adaptivity quantifies the information theoretic complexity of oracle optimization for parallel computations. We propose a new approximation algorithm based on the continuous greedy approach and prove that the algorithm could obtain a fractional solution with approximation ratio \begin{document}$ (1-e^{-{\gamma}^2}-\mathcal{O}(\epsilon)) $\end{document} in \begin{document}$ \mathcal{O}\left(\frac{\log n\log(k/\gamma\epsilon)} {\epsilon^{-2} \log n\log(1/\gamma)-\epsilon^{-1}\log(1-\epsilon)}\right) $\end{document} adaptive rounds. We then use the contention resolution schemes to convert the fractional solution to a discrete one with \begin{document}$ \gamma(1-e^{-1})(1-e^{-{\gamma}^2}-\mathcal{O}(\epsilon)) $\end{document} -approximation.