A Faster Tight Approximation for Submodular Maximization Subject to a Knapsack Constraint

The problem of maximizing a monotone submodular function subject to a knapsack constraint admits a tight $(1-e^{-1})$-approximation: exhaustively enumerate over all subsets of size at most three and extend each using the greedy heuristic [Sviridenko, 2004]. We prove it suffices to enumerate only over all subsets of size at most two and still retain a tight $(1-e^{-1})$-approximation. This improves the running time from $O(n^5)$ to $O(n^4)$ queries. The result is achieved via a refined analysis of the greedy heuristic.