  Submodular maximization is a classic algorithmic problem with multiple
applications in data mining and machine learning; there, the growing need to
deal with massive instances motivates the design of algorithms balancing the
quality of the solution with applicability. For the latter, an important
measure is the adaptive complexity, which captures the number of sequential
rounds of parallel computation needed by an algorithm to terminate. In this
work we obtain the first constant factor approximation algorithm for
non-monotone submodular maximization subject to a knapsack constraint with
near-optimal $O(\log n)$ adaptive complexity. Low adaptivity by itself,
however, is not enough: a crucial feature to account for is represented by the
total number of function evaluations (or value queries). Our algorithm asks
$\tilde{O}(n^2)$ value queries, but can be modified to run with only
$\tilde{O}(n)$ instead, while retaining a low adaptive complexity of
$O(\log^2n)$. Besides the above improvement in adaptivity, this is also the
first combinatorial approach with sublinear adaptive complexity for the problem
and yields algorithms comparable to the state-of-the-art even for the special
cases of cardinality constraints or monotone objectives.
