Rozkład funkcji podmodularnej

Biorąc podmodular funkcji $f$ na $\Omega=X_1\cup X_2$ gdzie $X_1$ i $X_2$ są rozłączni i $f(S)=f_1(S\cap X_1)+f_2(S\cap X_2)$ . Tutaj $f_1$ i $f_2$ są podmodularne $X_1$ i $X_2$ odpowiednio.

Tutaj $X_1,X_2,f_1,f_2$ są nieznane i dostęp tylko do zapytania o wartość $f$ jest podawany. Czy istnieje algorytm politime, który znajdzie $X_1$ . Jeśli istnieje wiele opcji dla $X_1$ każdy z nich powinien być w porządku.

Kilka myśli. Jeśli znajdziemy jakieś dwa elementy $t_1,t_2$ tak, że oba należą do $X_1$ lub należą do $X_2$ wtedy możemy je połączyć i postępować rekurencyjnie. Ale nie jest jasne, jak wdrożyć taki krok.

ds.algorithms submodularity Ashwinkumar BV
źródło

Chcesz to powiedzieć?

f (S) = f_{1} (S \cap X_{1}) + f_{2} (S \cap X_{2})

$f(S) = f_1(S \cap X_1) + f_2(S \cap X_2)$ gdzie

f_{1}

$f_1$ i

f_{2}

$f_2$ są podmodularne

X_{1}

$X_1$ i

X_{2}

$X_2$ odpowiednio?

Chandra Chekuri

Tak, naprawdę to miałem na myśli. Dzięki za wskazanie literówki, poprawię to.

Ashwinkumar BV,

Nie jestem pewien, czy to, co mówię poniżej, jest poprawne, ale oto pomysł. Weź dowolny element

e \in Ω

$e \in \Omega$ . Gdyby

f (e) = f_{Ω - e} (e)

$f(e) = f_{\Omega-e}(e)$ następnie

e

$e$ reszta elementów nie ma wpływu, więc możemy wybrać

X_{1} = {e}

$X_1 = \{e\}$ i

X_{2} = Ω - {e}

$X_2 = \Omega-\{e\}$ . W przeciwnym razie pozwól

X

$X$ być minimalnym podzbiorem uwzględniającym włączenie

Ω - e

$\Omega-e$ takie, że

f (e) > f_{X} (e)

$f(e) > f_X(e)$ . To by się wydawało

X \cup {e}

$X \cup \{e\}$ powinny znajdować się w tej samej partycji, a zatem możemy zmniejszyć zestaw do jednego elementu i powtórzyć, jeśli jest on znacznie mniejszy niż

Ω

$\Omega$ , w przeciwnym razie dochodzimy do wniosku, że nie istnieje pożądana partycja.

Chandra Chekuri

Postanowiłem zamienić komentarz w odpowiedź.

Chandra Chekuri

Rozkład funkcji podmodularnej

Odpowiedzi: