 Solution

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

No. Take the hypergraph with

V = {a, b}

and its single hyperedge

{a, b}

1

. Then

{a} \subseteq V

but

f ({a}) = 1 > 0 = f (V)

, violating the monotone set function property. This example already has strictly positive weights.

 New to topics? Read the docs here!