Submodular Definition < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei f eine nichtnegative submodulare Funktion uns sei [mm] \overline{f}:2^{E} \to \IR [/mm] gegeben durch [mm] \overline{f}(\emptyset):=0 [/mm] und [mm] \overline{f}(A)=min\{f(X): X\supseteq A\} [/mm] für alle nichtleeren Mengen A [mm] \subseteq [/mm] E.
Zeige: [mm] \overline{f} [/mm] ist submodular und monoton wachsend mit [mm] P_{f}=P_{\overline{f}} [/mm] |
Hey zusammen! Wäre nett wenn mir jemand von euch sagen könnte, ob ich mit meinem Ansatz auf dem Richtigen Weg bin, bzw. ob sich da ein Fehler eingeschlichen hat. Danke vielmals!
zu zeigen Submodularität, d.h. [mm] \overline{f}(A)+\overline{f}(B)\ge\overline{f}(A\cup B)+\overline{f}(A\cap [/mm] B)
[mm] \overline {f}(A)+\overline{f}(B)
[/mm]
[mm] =min\{f(X) : X\supseteq A\}+min\{f(Y) : Y\supseteq B\} [/mm]
[mm] \ge min\{f(X)+f(Y) : X\supseteq A, Y\supseteq B\}
[/mm]
[mm] \ge min\{f(X \cup Y)+f(X \cap Y)X\supseteq A, Y\supseteq B\}
[/mm]
LG Susi
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Do 18.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
