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

Table of contents
- Solution 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.

 Ancestors (11)

 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