We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined on a set of weighted items under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of \(0.357\) for this problem.
This greedy algorithm starts with an empty solution set and iteratively generates a feasible solution by packing items with maximum relative marginal gain to the current solution, stopping when adding the next item would violate the knapsack constraint. Then it compares the objective value of the current solution to that of the element that was last attempted to be packed and returns the one with the greater objective value.
Hence, it relies on the existence of an exact polynomial-time incremental oracle that identifies, in each iteration, an item with maximum relative marginal gain to the current solution.
We generalize the known approximation result for this greedy algorithm to the presence of only an approximate incremental oracle that identifies in each iteration of the greedy algorithm an item whose relative marginal gain approximates the maximum relative marginal gain by at least \(\frac{1}{\alpha}\), with \(\alpha \geq 1\) fixed.
Furthermore, we present an approximation result for a variant of the greedy algorithm in which an approximate incremental oracle is used in the first iteration of the greedy algorithm, and an exact incremental oracle is used in all subsequent iterations.