Nearly Linear Oracle Algorithms for Submodular Maximization under Matroid and Polymatroid Constraints

We give nearly linear oracle algorithms for monotone submodular maximization under general matroid constraints and monotone DR-submodular maximization over integral polymatroids, with expected approximation $1-1/e-\epsilon$ and polynomial accuracy dependence. Short exchange walks and controlled endpoint bias make rounding inexpensive. For independence-oracle fractional optimization, private filtering progress and a smaller contraction minor support multilevel preprocessing. For polymatroids, we obtain nearly linear query complexity even at exponentially large numerical rank. Random gaps between capacity scales permit a nearly feasible product relaxation, while an integer baseline removes absolute capacity size from marginal threshold ranges. Poisson smoothing and colors allow large count increments; geometric searches with analytical shadow counts and aggregate latent-error concentration keep tests and samples inexpensive. A final shrink and approximate local covering complete the construction. The polymatroid algorithm uses $O(n{\epsilon }^{-9}{\Xi }_{\epsilon }^3)$ value queries and $O(n{\epsilon }^{-11}{\Xi }_{\epsilon }^3)$ expected integer-feasibility queries, where ${\Xi }_{\epsilon }=\log (2n/\epsilon )+\log \log (r+3)$. An $\Omega (n)$ feasibility lower bound holds at rank exactly $2^n$. All outputs are feasible on every run; the bounds count ordinary oracle calls rather than bit complexity.