by A. Krause, C. Guestrin

Abstract:

Many set functions F in combinatorial optimization satisfy the diminishing returns property F (A ∪ X ) − F (A) ≥ F (A′ ∪ X ) − F (A′ ) for A ⊂ A′ . Such functions are called submodular. A result from Nemhauser et.al. states that the problem of selecting k-element subsets maximizing a nondecreasing submodular function can be approximated with a constant factor (1 − 1/e) performance guarantee. Khuller et.al. showed that for the special submodular function involved in the MAX-COVER problem, this approximation result generalizes to a budgeted setting under linear nonnegative cost-functions. They proved a (1−1/e) approximation guarantee for a modified Greedy algorithm, 2 and show how a (1 − 1/e) guarantee can be achieved using partial enumeration. In this note, we extend their results to general submodular functions. Motivated by the problem of maximizing entropy in discrete graphical models, where the submodular objective cannot be evaluated exactly, we generalize our result to account for absolute errors.

Reference:

A Note on the Budgeted Maximization on Submodular Functions A. Krause, C. GuestrinTechnical report CMU-CALD-05-103, Carnegie Mellon University, 2005

Bibtex Entry:

@techreport{krause05note) − F (A) ≥
F (A′ ∪ {X }) − F (A′ ) for A ⊂ A′ . Such functions are called submodular. A result from Nemhauser et.al. states that
the problem of selecting k-element subsets maximizing a nondecreasing submodular function can be approximated
with a constant factor (1 − 1/e) performance guarantee. Khuller et.al. showed that for the special submodular
function involved in the MAX-COVER problem, this approximation result generalizes to a budgeted setting under
linear nonnegative cost-functions. They proved a (1−1/e) approximation guarantee for a modified Greedy algorithm, 2
and show how a (1 − 1/e) guarantee can be achieved using partial enumeration. In this note, we extend their results to general submodular functions. Motivated by the problem of maximizing entropy in discrete graphical models, where the submodular objective cannot be evaluated exactly, we generalize our result to account for absolute errors.},
	author = {Andreas Krause and Carlos Guestrin},
	institution = {Carnegie Mellon University},
	number = {CMU-CALD-05-103},
	title = {A Note on the Budgeted Maximization on Submodular Functions},
	year = {2005}}