Zerlegen einer submodularen Funktion

9

Gegeben ist eine submodulare Funktion auf Ω = X 1X 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Ω=X1X2X1X2f(S)=f1(SX1)+f2(SX2)f1f2X1X2

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.X1,X2,f1,f2fX1X1

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.t1,t2X1X2

Ashwinkumar BV
quelle
2
Wollen Sie damit sagen, dass wobei f 1 und f 2 auf X 1 bzw. X 2 submodular sind ? f(S)=f1(SX1)+f2(SX2)f1f2X1X2
Chandra Chekuri
Ja, das habe ich wirklich gemeint. Vielen Dank, dass Sie auf den Tippfehler hingewiesen haben. Ich werde ihn korrigieren.
Ashwinkumar BV
3
eΩf(e)=fΩe(e)eX1={e}X2=Ω{e}XΩef(e)>fX(e)X{e}Ω
2
Beschlossen, den Kommentar in eine Antwort zu verwandeln.
Chandra Chekuri

Antworten:

5

eΩf(e)=fΩe(e)eX1={e}X2=Ω{e}XΩef(e)>fX(e)X{e}X{e}=Ω

Chandra Chekuri
quelle