In this paper, we investigate the two phases deletion robust submodular maximization over a matroid constraint. For monotone objectives, in the first phase, we propose a parallel algorithm that reduces the adaptivity to \(O_{\varepsilon }(\log n\cdot \log r)\) , from the previous bound of \(O_{\varepsilon }(n \cdot \log r)\) (Dütting et al., ICML, pp. 5671–5693, 2022), with a query complexity of \(O_{\varepsilon }(nr\log r)\) . Although the query complexity is slightly higher, our algorithm achieves an exponential reduction in adaptive complexity, offering a favorable trade-off. The approximation ratio and summary size match previous results. The complete two phases algorithm achieves a \((2+\alpha +O(\varepsilon ))\) -approximation for any \(\varepsilon \in (0, \frac{1}{5})\) , where \(\alpha \) is the approximation of an algorithm for a matroid constrained monotone submodular maximization. The summary size is \(O_{\varepsilon }(r+d\log r)\) , where d denotes the number of deleted elements. For non-monotone objectives, the extended parallel algorithm achieves asymptotically the same adaptive complexity and query complexity. For any \(\varepsilon \in (0, \frac{1}{6})\) , the overall approximation guarantee becomes \((2+\beta +O(\varepsilon ))\) -approximation, where \(\beta \) is the approximation ratio for non-monotone submodular maximization. The summary size is bounded by \(O_{\varepsilon }((r+d)\log r)\) .
