Submodular Maximization Subject to a Knapsack Constraint:
     Combinatorial Algorithms with Near-Optimal Adaptive Complexity

           Georgios Amanatidis 1 Federico Fusco 2 Philip Lazos 2 Stefano Leonardi 2
               Alberto Marchetti-Spaccamela 2 Rebecca Reiffenhauser 2

            Abstract                cut functions in graphs and coverage functions.
   The growing need to deal with massive instances      Submodularity is often implicitly associated with mono-
   motivates the desi ...