  We consider the problem of maximizing a monotone submodular function subject
to a knapsack constraint. Our main contribution is an algorithm that achieves a
nearly-optimal, $1 - 1/e - \epsilon$ approximation, using
$(1/\epsilon)^{O(1/\epsilon^4)} n \log^2{n}$ function evaluations and
arithmetic operations. Our algorithm is impractical but theoretically
interesting, since it overcomes a fundamental running time bottleneck of the
multilinear extension relaxation framework. This is the main approach for
obtaining nearly-optimal approximation guarantees for important classes of
constraints but it leads to $\Omega(n^2)$ running times, since evaluating the
multilinear extension is expensive. Our algorithm maintains a fractional
solution with only a constant number of entries that are strictly fractional,
which allows us to overcome this obstacle.
