Konvolution - Polymatroid < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) überfällig | Datum: | 11:50 Di 02.12.2008 | Autor: | Schobbi |
Aufgabe | Sei f: [mm] 2^{E}\to \IR [/mm] submodular und sei a [mm] \in \IR^{E}. [/mm] Dann besitzt die Konvolution [mm] (f|a)(X):=min_{Y}\{f(Y)+a(X \backslash Y):Y \subseteq X\} [/mm] das folgende (erweiterte) Polymatroid [mm] EP_{f|a}=\{x \in EP_{f} : x \le a\} [/mm] bzw. [mm] P_{f|a}=\{x \in P_{f} : x \le a\} [/mm] |
Guten Morgen zusammen!
Die obige Aufgabe schein relativ einleuchtend zu sein, jedoch fehlt mir der Ansatz hierfür einem mathematischen Beweis zu führen, vielleicht könnt ihr mir da auf die Sprünge helfen. DANKE!
[mm] P_{f}:=\{ x \in \IR^{E} : x \ge 0, x(A) \le f(A) \forall A \subseteq E\}
[/mm]
[mm] EP_{f}:=\{ x \in \IR^{E} : x(A) \le f(A) \forall A \subseteq E\}
[/mm]
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 12:20 Do 04.12.2008 | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|