erweitertes Polymatroid < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] f:2^{E}\to\IR [/mm] submodular mit [mm] f(\emptyset)=0. [/mm]
Zeige, dass gilt: [mm] max_{x}\{x(E) : x \in EP_{f}, x\le0 \}=max_{x}\{x^{-}(E) : x \in B_{f}\} [/mm] mit [mm] x^{-}(E) [/mm] := [mm] \summe_{e\in E}min\{0,x_{e}\} [/mm] |
Guten Morgen zusammen! Ich habe ein Problem beim Beweis von obiger Aussage. Vielleicht könnt ihr mir dabei helfen! Danke schon mal im Voraus!
Die Menge [mm] EP_{f} [/mm] bezeichnet das erweiterte Polymatroid von f, also [mm] EP_{f}=\{x\in \IR^{n} : x(A) \le f(A) \forall A \subseteq E\} [/mm] ebenso definiert sich die Menge [mm] B_{f} [/mm] als Basispolytop [mm] B_{f}=\{x \in \IR^{n} : x(A) \le f(A) \forall A\subseteq E, x(E)=f(E)\}
[/mm]
Theoretisch ist mir klar, dass wir im allgemeinen nicht wissen wie die Eckpunkte aussehen, somit betrachten wie das Basispolyeder indem wir die Ecken kennen. Weiter ist klar, dass folgendes gilt: [mm] min\{f(A) : A\subseteq E\}=max_{x}\{x(E) : x \in EP_{f}, x \le 0\}
[/mm]
Wäre schön wenn ihr mir bei meiner Aufgabe helfen könntet.
LG Susi
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Do 18.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
