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 of [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.