 Solution

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

No for arbitrary signed weights. Give the same single hyperedge weight

- 1

. For

A = {a}

and

B = {b}

f (A) + f (B) = - 2 < 0 = f (A \cap B) + f (A \cup B) .

This directly violates the defining inequality for a submodular set function.

 New to topics? Read the docs here!