लगातार सूचकांकों के लिए कमजोर submodularity
लश्कर $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ द्वारा परिभाषित किया जाना है $f(x,y) = \frac{x^2}{y}$। लश्कर$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}^+$ आदेश दिया जाए ताकि $\frac{x_1}{y_1} \leq \dots \leq \frac{x_n}{y_n}$। सेट फ़ंक्शन को परिभाषित करें$F\colon 2^n \rightarrow \mathbf{R}$ द्वारा द्वारा $F(S) = \frac{(\sum_{i \in S}x_i)^2}{\sum_{i \in S}y_i}$ के लिये $S \subseteq \left\lbrace 1, \dots n\right\rbrace$
$F$ सबमॉडुलर होने में विफल हो सकते हैं, यहां तक कि के लिए भी $X$ सकारात्मक - के लिए $X = \left\lbrace0, 7, 8, 9\right\rbrace$, $Y = \left\lbrace4, 7, 1, 1\right\rbrace$ लेना $$ \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} $$ तथा $$ F(S) + F(T) \approx 80.1667 \\ F(S \cup T) + F(S \cap T) \approx 125.3077 $$
मैं सोच $F$ हालांकि, दूसरे शब्दों में, अंतराल के लिए सबमॉड्यूलर है $$ F(S) + F(T) \geq F(S \cup T) + F(S \cap T) $$
के लिये $S$, $T$ फार्म का अंतराल $\left\lbrace j, j+1, \dots k\right\rbrace$, के लिये $j \leq k$के किसी भी विनिर्देश के लिए $X$, $Y$। मैं यह साबित नहीं कर पाया हूं - क्या कोई भी साबित कर सकता है या एक प्रतिसाद प्रदान कर सकता है?
जवाब
निम्नांकित प्रावधान के साथ सबमॉड्यूलरिटी निहित है: ओपी में, $F(\emptyset)$अपरिभाषित है। आइए हम इसे परिभाषित करते हैं$0$।
लश्कर $$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.$$ व्यापकता (हानि) के नुकसान के बिना, $S$ तथा $T$ गैर-रिक्त हैं, और अंतराल के बाएं छोर $S$ अंतराल के बाएं छोर से अधिक नहीं है $T$। जाहिर है,$t_1,t_2,t_3\ge0$। यह मानते हुए$t_1,t_2,t_3>0$, शर्त $\frac{x_1}{y_1}\le\dots\le\frac{x_n}{y_n}$ का तात्पर्य $$\frac{s_1}{t_1}\le\frac{s_2}{t_2}\le\frac{s_3}{t_3}.\tag{1}$$
ये स्थितियाँ और अधिक स्पष्ट हैं $$\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}$$ अर्थात्, $$F(S)+F(T)\ge F(S\cup T)+F(S\cap T)$$ अगर $t_1,t_2,t_3>0$। मामलों में से एक के साथ$t_j$और (तत्संबंधी) $s_j$के बराबर है $0$ समान हैं, और सरल हैं।
इस प्रकार, $F$ सबमॉड्यूलर है।
(1) में पहली असमानता को साबित करने के लिए (कहने) $r_i:=x_i/y_i$, $j:=\max(S\setminus T)$, तथा $k:=\min(S\cap T)$। फिर$x_i=r_i y_i$, $r_i$ में बढ़ रहा है $i$, तथा $j<k$। इसलिए,$s_1\le r_j t_1$, तथा $s_2\ge r_k t_2$, तथा $r_j\le r_k$। ये असमानताएं (1) में पहली असमानता को दर्शाती हैं। (1) में दूसरी असमानता काफी समान साबित होती है।
साबित करने के लिए (2), वहां बदलें $s_j$ द्वारा द्वारा $R_jt_j$, कहां है $R_j:=s_j/t_j$, ताकि, (1), $R_1\le R_2\le R_3$। तब व्युत्पन्न में ध्यान दें$R_3$ (2) के बाएँ और दाएँ हाथ के बीच का अंतर (के साथ) $s_j$ द्वारा प्रतिस्थापित $R_jt_j$) है $$\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.$$ तो, wlog $R_3=R_2$किस स्थिति में (2) को फिर से लिखा जा सकता है $$\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}$$ जो स्पष्ट रूप से सच है।
हम यह भी देख सकते हैं कि $t_1,t_2,t_3>0$जब तक असमानता (2) सख्त है $R_1=R_2=R_3$।
इसके अलावा, संबंधित परिस्थितियों में साबित करना (2) वास्तविक बीजीय ज्यामिति की एक साधारण समस्या है, जिसे एल्गोरिथम / विचारपूर्वक नियंत्रित किया जा सकता है, जैसा कि एक गणितज्ञ नोटबुक की निम्न छवि से देखा जाता है (इसे बढ़ाने के लिए छवि पर क्लिक करें):
