  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 \emph{adaptive complexity}, capturing the
number of sequential rounds of parallel computation needed. In this work we
obtain the first \emph{constant factor} approximation algorithm for
non-monotone submodular maximization subject to a knapsack constraint with
\emph{near-optimal} $O(\log n)$ adaptive complexity. Low adaptivity by itself,
however, is not enough: one needs to account for the total number of function
evaluations (or value queries) as well. 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 \emph{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. Finally, we showcase our algorithms'
applicability on real-world datasets.
