We consider the problem of maximizing a nondecreasing submodular set function over various constraint structures. Specifically, we explore the performance of the greedy algorithm, and a related variant, the locally greedy algorithm in solving submodular function maximization problems. Most classic results on the greedy algorithm and its variant assume the existence of an optimal polynomial-time incremental oracle that identifies, in each iteration, an element of maximum incremental value to the solution at hand. In the presence of only an approximate incremental oracle, we generalize the performance bounds of the greedy algorithm and its variant in maximizing submodular functions over (i) uniform matroids, (ii) partition matroids, and (iii) general independence systems. Subsequently, we reinterpret and, thereby, unify and improve various algorithmic results in the recent literature for problems that are specific instances of maximizing monotone submodular functions in the presence of an approximate incremental oracle. This includes results for the Separable Assignment problem, the AdWords Assignment problem, the Set k-Cover problem, basic utility games, winner determination in combinatorial auctions, and related problem variants.
Citation
Working Paper, Massachusetts Institute of Technology, 2007.
Article
View Revisiting the Greedy Approach to Submodular Set Function Maximization