Optimization Online


Revisiting the Greedy Approach to Submodular Set Function Maximization

Pranava R. Goundan(pranava***at***alum.mit.edu)
Andreas S. Schulz(schulz***at***mit.edu)

Abstract: 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.

Keywords: approximation algorithms; greedy algorithm; matroids; submodular functions

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: Working Paper, Massachusetts Institute of Technology, 2007.

Download: [PDF]

Entry Submitted: 08/01/2007
Entry Accepted: 08/01/2007
Entry Last Modified: 08/01/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society