 Solution

ID: past-exam-of-the-integer-programming-course-of-the-university-of-oxford/2011/1/c/solution

E

, a submodular rank function is a set function

r : 2^{E} \to R

with the following properties:

r (\emptyset) = 0, A \subseteq B ⟹ r (A) \leq r (B), r (A) + r (B) \geq r (A \cup B) + r (A \cap B), r (A \cup {e}) - r (A) \in {0, 1} (e \in / A) .

These are normalization, monotonicity, submodularity, and unit integer increments. In particular its values are nonnegative integers with

r (A) \leq ∣ A ∣

. Equivalently, one can require an integer-valued normalized monotone submodular function with

r ({e}) \leq 1

: diminishing returns then bounds every marginal increment by one. A general real-valued submodular function need not be a matroid rank.

 New to topics? Read the docs here!