Parallelizing greedy for submodular set function maximization in\n matroids and beyond

We consider parallel, or low adaptivity, algorithms for submodular function\nmaximization. This line of work was recently initiated by Balkanski and Singer\nand has already led to several interesting results on the cardinality\nconstraint and explicit packing constraints. An important open problem is the\nclassical setting of matroid constraint, which has been instrumental for\ndevelopments in submodular function maximization. In this paper we develop a\ngeneral strategy to parallelize the well-studied greedy algorithm and use it to\nobtain a randomized $\\left(\\frac{1}{2} - \\epsilon\\right)$-approximation in\n$\\operatorname{O}\\left( \\frac{\\log^2 n}{\\epsilon^2} \\right)$ rounds of\nadaptivity. We rely on this algorithm, and an elegant amplification approach\ndue to Badanidiyuru and Vondr\\'ak to obtain a fractional solution that yields a\nnear-optimal randomized $\\left( 1 - 1/e - \\epsilon \\right)$-approximation in\n$O\\left( {\\frac{\\log^2 n}{\\epsilon^3}} \\right) $ rounds of adaptivity. For\nnon-negative functions we obtain a $\\left( {3-2\\sqrt{2}}\\right)$-approximation\nand a fractional solution that yields a $\\left( {\\frac{1}{e} -\n\\epsilon}\\right)$-approximation. Our approach for parallelizing greedy yields\napproximations for intersections of matroids and matchoids, and the\napproximation ratios are comparable to those known for sequential greedy.\n