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

Weź dowolny element $e \in \Omega$ . Gdyby $f(e) = f_{\Omega-e}(e)$ następnie $e$ reszta elementów nie ma wpływu, więc możemy wybrać $X_1 = \{e\}$ i $X_2 = \Omega-\{e\}$ . W przeciwnym razie pozwól $X$ być minimalnym podzbiorem uwzględniającym włączenie $\Omega-e$ takie, że $f(e) > f_X(e)$ . Następnie $X \cup \{e\}$ powinien znajdować się na tej samej partycji. Gdyby $X \cup \{e\} = \Omega$ dochodzimy do wniosku, że nie ma pożądanej partycji, w przeciwnym razie zmniejszamy ten zestaw do jednego elementu i powtarzamy.

— Chandra Chekuri
źródło