 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation/1/c/ii/solution

For every

S \subseteq V

and

x \in / S

, including

S = \emptyset

Δ_{x} f (S) = max {0, w (x) - f (S)} .

For the empty set, this uses

w (x) \geq f (\emptyset) = min_{v \in V} w (v)

. The monotone set function property from (i) gives

f (A) \leq f (B)

when

A \subseteq B

. Consequently

max {0, w (x) - f (A)} \geq max {0, w (x) - f (B)} .

Thus diminishing returns holds, so $f$ is a submodular set function by (b).

 New to topics? Read the docs here!