 Solution

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

f : 2^{V} \to R

, the four properties are:

A normalised set function satisfies $f (\emptyset) = 0$ .
A nonnegative function satisfies $f (S) \geq 0$ for every $S \subseteq V$ .
A monotone set function satisfies $f (A) \leq f (B)$ whenever $A \subseteq B \subseteq V$ .
A symmetric set function satisfies $f (S) = f (V ∖ S)$ for every $S \subseteq V$ .

Here monotone set function means nondecreasing under inclusion; it does not require strict increase.

 New to topics? Read the docs here!