Greedy algorithms with imprecise oracles for submodular knapsack problems

Abstract We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined over a set of elements with associated weights under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of $$\varvec{0.357}$$ 0.357 for this problem. This greedy algorithm starts with an empty solution set and iteratively adds elements with maximum relative marginal gain to the current solution, stopping when adding the next element would violate the knapsack constraint. Then it compares the objective value of the current solution set to that of the element that exceeded the knapsack constraint and returns the one with the greater objective value. Therefore, this algorithm relies on the existence of an exact incremental oracle that identifies, in each iteration, an element 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 iteration $$\varvec{i}$$ i of the greedy algorithm an element whose relative marginal gain is at least a $$\varvec{\frac{1}{\alpha _i}}$$ 1 α i -fraction, with $$\varvec{\alpha _i \ge 1}$$ α i ≥ 1 , of the maximum relative marginal gain. 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.