Wzmocnienia submodularności

13

Ustawiona funkcja jest monotoniczna podmodularna, jeśli dla wszystkich , $f$ $A,B$

f (A) + f (B) \geq f (A \cup B) + f (A \cap B) .

$f(A) + f(B) \geq f(A \cup B) + f(A \cap B).$

Silniejszą właściwością jest Biorąc

\begin{matrix} f (A) + f (B) + f (C) + f (A \cup B \cup C) \geq \\ f (A \cup B) + f (B \cup C) + f (A \cup C) + f (A \cap B \cap C) . \end{matrix}

$\begin{multline*} f(A) + f(B) + f(C) + f(A\cup B\cup C) \geq \\f(A\cup B) + f(B\cup C) + f(A\cup C) + f(A \cap B \cap C). \end{multline*}$

, ta właściwość implikuje monotoniczną submodularność.

C = A \cup B

$C = A\cup B$

Czy ta właściwość jest znana?

tło

Ta właściwość pojawiła się podczas próby scharakteryzowania funkcji pokrycia. Biorąc pod uwagę niektóre ważonej świat (wszystkie ilości są dla ujemnych) oraz rodzinę podzbiorów funkcja pokrycia jest definiowana dla w stosunku do całkowitego ciężaru elementów zawartych w zestawach . Funkcja jest zawsze monotoniczna i podmodularna. Odwrotna sytuacja nie jest prawdą. $U$ $X$ $U$ $f(S)$ $S \subseteq X$ $S$ $f$

Właściwość, o której mowa, oznacza, że jest funkcją pokrycia w przypadku . Podobne, bardziej skomplikowane właściwości pracować dla większej . Wszystkie te właściwości spełniają funkcje pokrycia, więc jest to pełna charakterystyka. $f$ $|X| = 3$ $X$

ds.algorithms approximation-algorithms submodularity Yuval Filmus
źródło

13

$k^{th}$

$f(B)-f(A)\ge 0$ $A\subseteq B$

$(f(A\cup B)-f(B))-(f(A)-f(A\cap B))\le 0$

$n$

Coś podobnego było już znane z prawdopodobieństwem. Funkcję pokrycia można również traktować jako miarę prawdopodobieństwa (aż do stałej skalowania). Jedyne odniesienie, które udało mi się wykopać, to strona 439 z książki Fellera o prawdopodobieństwie.

Ashwinkumar BV
źródło

f (A \cup {x}) \geq f (A)

$f(A \cup \{x\}) \geq f(A)$

f (A \cup {x}) + f (A \cup {y}) \geq f (A \cup {x, y}) + f (A)

$f(A \cup \{x\}) + f(A \cup \{y\}) \geq f(A \cup \{x,y\}) + f(A)$

A, B

$A,B$

7

\begin{matrix} f (A \cap B) + f (A \cap C) + f (B \cap C) + f ((A \cap B) \cup (A \cap C) \cup (B \cap C)) \geq \\ f (A \cap (B \cup C)) + f (B \cap (A \cup C)) + f (C \cap (A \cup B)) + f (A \cap B \cap C) . \end{matrix}

$\begin{multline*} f(A \cap B) + f(A \cap C) + f(B \cap C) + f((A \cap B) \cup (A \cap C) \cup (B \cap C)) \geq \\ f(A \cap (B \cup C)) + f(B \cap (A \cup C)) + f(C \cap (A \cup B)) + f(A \cap B \cap C). \end{multline*}$ Warunek „agregacji” jest wspomniany w pracy „Charakterystyka stożka funkcji pseudo-boolowskich poprzez nierówności typu supermodularności” Crammy, Hammera i Holtzmana (nierówność (4)), która jest częścią rzadkiego zbioru „Quantitative Methoden” in den Wirtschaftswissenschaften ". Ten warunek powinien być taki sam jak mój.

\begin{matrix} f (A) + f (B) + f (C) + f (A \cap B \cap C) \geq \\ f (A \cup B \cup C) + f (A \cap B) + f (A \cap C) + f (B \cap C) . \end{matrix}

$\begin{multline*} f(A) + f(B) + f(C) + f(A \cap B \cap C) \geq \\ f(A \cup B \cup C) + f(A \cap B) + f(A \cap C) + f(B \cap C). \end{multline*}$

C = \emptyset

$C = \varnothing$

Yuval Filmus
źródło

Wzmocnienia submodularności

tło

Odpowiedzi: