Before revision: 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 twoand still retain a tight (1-e^{-1 of the greedy heuristic.
After revision: 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 three to two; (2) present an improved upper bound of 0.42945 for the classic algorithm which returns the better between a single element and the output of the greedy heuristic.