Note on Submodular Function Optimization, Minimization and Maximization, Lazy Greedy
Published:
This blog is based on week 10 of PKU Algorithms for Big Data Analysis.
Introduction of Submodular Functions
Definition 1.1 (Submodular Function).
Let ( V ) be a finite ground set. A set function
[
f : 2^{V} \rightarrow \mathbb{R}
]
is called submodular if for all subsets ( A, B \subseteq V ),
[
f(A) + f(B) \geq f(A \cup B) + f(A \cap B).
]
Definition 1.2 (Diminishing Returns Property).
A set function ( f : 2^{V} \rightarrow \mathbb{R} ) is said to satisfy the diminishing returns property if for all ( A \subseteq B \subseteq V ) and all ( x \in V \setminus B ),
[
f(A \cup {x}) - f(A) \geq f(B \cup {x}) - f(B).
]