Słaba submodularność dla kolejnych indeksów
Wynajmować$f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$być zdefiniowane przez$f(x,y) = \frac{x^2}{y}$. Wynajmować$X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$,$Y = \left\lbrace y_1, \dots, y_n\right\rbrace \subseteq \mathbf{R}^+$być uporządkowane tak, że$\frac{x_1}{y_1} \leq \dots \leq \frac{x_n}{y_n}$. Zdefiniuj ustawioną funkcję$F\colon 2^n \rightarrow \mathbf{R}$za pomocą$F(S) = \frac{(\sum_{i \in S}x_i)^2}{\sum_{i \in S}y_i}$dla$S \subseteq \left\lbrace 1, \dots n\right\rbrace$
$F$może nie być submodularny, nawet dla$X$pozytywny - dla$X = \left\lbrace0, 7, 8, 9\right\rbrace$,$Y = \left\lbrace4, 7, 1, 1\right\rbrace$Brać$$ \begin{align} S &= \left\lbrace 1, 3\right\rbrace \\ T &= \left\lbrace0, 2, 3\right\rbrace \\ S \cap T &= \left\lbrace 3\right\rbrace\\ S \cup T &= \left\lbrace 0, 1, 2, 3\right\rbrace \\ \end{align} $$oraz$$ F(S) + F(T) \approx 80.1667 \\ F(S \cup T) + F(S \cap T) \approx 125.3077 $$
Myślę$F$jest submodularny dla interwałów, innymi słowy$$ F(S) + F(T) \geq F(S \cup T) + F(S \cap T) $$
dla$S$,$T$interwały formy$\left\lbrace j, j+1, \dots k\right\rbrace$, dla$j \leq k$, dla dowolnej specyfikacji$X$,$Y$. Nie udało mi się tego udowodnić - czy ktoś może udowodnić lub podać kontrprzykład?
Odpowiedzi
Submodularność obowiązuje, z następującym zastrzeżeniem: W PO$F(\emptyset)$jest nieokreślony. Zdefiniujmy to jako$0$.
Wynajmować$$s_1:=\sum_{S\setminus T}x_i,\quad s_2:=\sum_{S\cap T}x_i,\quad s_3:=\sum_{T\setminus S}x_i,$$ $$t_1:=\sum_{S\setminus T}y_i,\quad t_2:=\sum_{S\cap T}y_i,\quad t_3:=\sum_{T\setminus S}y_i.$$Bez utraty ogólności (wlog),$S$oraz$T$są niepuste, a lewy koniec przedziału$S$nie jest większa niż lewy punkt końcowy przedziału$T$. Oczywiście,$t_1,t_2,t_3\ge0$. Zarozumiały$t_1,t_2,t_3>0$, warunek$\frac{x_1}{y_1}\le\dots\le\frac{x_n}{y_n}$implikuje$$\frac{s_1}{t_1}\le\frac{s_2}{t_2}\le\frac{s_3}{t_3}.\tag{1}$$
Te warunki dodatkowo implikują$$\frac{(s_1+s_2)^2}{t_1+t_2}+\frac{(s_2+s_3)^2}{t_2+t_3}\ge\frac{(s_1+s_2+s_3)^2}{t_1+t_2+t_3}+\frac{s_2^2}{t_2}.\tag{2}$$To znaczy,$$F(S)+F(T)\ge F(S\cup T)+F(S\cap T)$$jeśli$t_1,t_2,t_3>0$. Przypadki z jednym z$t_j$'s (i odpowiadające$s_j$'s) równe$0$są podobne i prostsze.
Zatem,$F$jest submodułowy.
Aby udowodnić (powiedzmy) pierwszą nierówność w (1), niech$r_i:=x_i/y_i$,$j:=\max(S\setminus T)$, oraz$k:=\min(S\cap T)$. Następnie$x_i=r_i y_i$,$r_i$nie maleje w$i$, oraz$j<k$. Więc,$s_1\le r_j t_1$, oraz$s_2\ge r_k t_2$, oraz$r_j\le r_k$. Nierówności te implikują pierwszą nierówność w (1). Druga nierówność w (1) jest dość podobnie udowodniona.
Aby udowodnić (2), wymień tam$s_j$za pomocą$R_jt_j$, gdzie$R_j:=s_j/t_j$, aby przez (1),$R_1\le R_2\le R_3$. Zauważ więc, że pochodna in$R_3$różnicy między lewą i prawą stroną (2) (z$s_j$zastąpione przez$R_jt_j$) jest$$\frac{2 t_1 t_3 \left(\left(R_2-R_1\right) t_2+\left(R_3-R_1\right) t_3\right)}{\left(t_2+t_3\right) \left(t_1+t_2+t_3\right)}\ge0.$$Więc wlog$R_3=R_2$, w takim przypadku (2) można przepisać jako$$\frac{\left(R_1-R_2\right){}^2 t_1^2 t_3}{\left(t_1+t_2\right) \left(t_1+t_2+t_3\right)}\ge0,\tag{3}$$co jest oczywiście prawdą.
Możemy to również zobaczyć, za pomocą$t_1,t_2,t_3>0$, nierówność (2) jest ścisła, chyba że$R_1=R_2=R_3$.
Ponadto udowodnienie (2) w odpowiednich warunkach jest prostym problemem rzeczywistej geometrii algebraicznej, który można rozwiązać algorytmicznie/bezmyślnie, jak widać na poniższym obrazie notatnika Mathematica (kliknij na obrazek, aby go powiększyć):
