Let $f:2^V \rightarrow \mathbb{R}$ be a set function over $V$ that satisfies the following:

  1. $f(A \cap B) + f(A \cup B) \le f(A) + f(B)$
  2. $f(A \backslash B) + f(B \backslash A) \le f(A) + f(B)$.

Here are the questions:

  1. Cut function $c(\delta(\cdot))$ is known to satisfy both 1) and 2). Is there any other natural example of function satisfying both ?
  2. If $f$ satisfies 1), then we say $f$ is submodular. But is there a name for the property of function satisfying both 1) and 2) ? Or only 2) ?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.