Zerlegen einer submodularen Funktion

Gegeben ist eine submodulare Funktion auf Ω = X 1 ∪ X 2, wobei X 1 und X 2 disjunkt sind und f ( S ) = f 1 ( S ∩ X 1 ) + f 2 ( S ∩ X 2 ) . Hier sind f 1 und f 2 auf X 1 bzw. X 2 submodular .$f$$\Omega=X_1\cup X_2$$X_1$$X_2$$f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$$f_1$$f_2$$X_1$$X_2$

Hier sind unbekannt und es wird nur ein Wertabfragezugriff auf f gegeben. Dann gibt es einen Polytime-Algorithmus, der X 1 findet . Wenn es für X 1 mehrere Auswahlmöglichkeiten gibt , sollte eine davon in Ordnung sein.$X_1,X_2,f_1,f_2$$f$$X_1$$X_1$

Einige Gedanken. Wenn wir zwei beliebige Elemente so dass beide entweder zu X 1 oder zu X 2 gehören, können wir sie zusammenführen und rekursiv fortfahren. Es ist jedoch nicht klar, wie ein solcher Schritt umgesetzt werden soll.$t_1,t_2$$X_1$$X_2$

$e \in \Omega$$f(e) = f_{\Omega-e}(e)$$e$$X_1 = \{e\}$$X_2 = \Omega-\{e\}$$X$$\Omega-e$$f(e) > f_X(e)$$X \cup \{e\}$$X \cup \{e\} = \Omega$