Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 1 / a

Table of contents
- Solution a

Solution

For a set function

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.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version