Introduction
Submodularity arises naturally in a wide range of applications, including influence maximization [3 , 15 , 28 ] [32], feature selection [8 , 23 , 24 ] , sensor placement [14 , 17 ] , and data summarization [1 , 18 , 21 ] .
A standard approach for maximizing submodular objectives is forward greedy: starting from the empty set, the algorithm repeatedly adds a feasible element with the largest marginal gain. Furthermore, classical theoretical analysis also gives that, for monotone submodular functions, forward greedy can achieve a tight approximation ratio of 1 − 1 / e 1 - 1/e 1 − 1/ e [22 ] .
However, exact submodularity may be overly restrictive for many practical applications. Indeed, many real-world scenarios give rise to utility functions that are close to submodular. Important examples include variable selection for regression [5 , 6 , 16 ] , neural network pruning [8 ] and sparse optimal transport [20 ] . One of the most widely used notions for characterizing such close-to-submodular objectives is γ \gamma γ [5 , 6 , 25 ] . More specifically, a monotone set function f : 2 U → R + f: 2^{U} \to\mathbb{R}_{+} f : 2 U → R + γ \gamma γ A ⊆ C ⊆ U A \subseteq C \subseteq U A ⊆ C ⊆ U
∑ e ∈ C ∖ A ( f ( A ∪ { e } ) − f ( A ) ) ≥ γ ( f ( C ) − f ( A ) ) . \sum_{e \in C \setminus A} \left(f(A \cup\{e\}) - f(A)\right) \ge\gamma\left(f(C) - f(A)\right). e ∈ C ∖ A ∑ ( f ( A ∪ { e }) − f ( A ) ) ≥ γ ( f ( C ) − f ( A ) ) . This inequality quantifies the extent to which the joint gain f ( C ) − f ( A ) f(C) - f(A) f ( C ) − f ( A ) C ∖ A C \setminus A C ∖ A A A A γ = 1 \gamma= 1 γ = 1 [5 , 6 ] proved that standard forward greedy achieves a ( 1 − e − γ ) (1 - e^{-\gamma}) ( 1 − e − γ ) γ \gamma γ [13 ] .
Beyond the cardinality constraints considered above, many of real-world applications also require us to obey additional structural restrictions, such as diversity and fairness, which can be naturally modeled by matroid constraints. For normalized monotone submodular functions, Fisher et al. [9 ] showed that standard forward greedy can attain a 1 / 2 1/2 1/2 [11 ] established an approximation guarantee of 0.4 γ 2 1 + γ r \frac{0.4\gamma^{2}}{1+\sqrt{\gamma}r} 1 + γ r 0.4 γ 2 [30 ] constructed a family of bad instances showing that, for every fixed γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) O ( γ ( 1 − γ ) 2 log ( n − 1 ) ) O\left(\frac{\gamma}{(1-\gamma)^{2}\log(n-1)}\right) O ( ( 1 − γ ) 2 l o g ( n − 1 ) γ ) n n n
Specifically, letting R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r ) γ \gamma γ r r r
Theorem 1.1. For every γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] r ≥ 2 r \ge2 r ≥ 2 B γ ≜ 2 − γ + γ 2 B_{\gamma} \triangleq2-\gamma+\gamma^{2} B γ ≜ 2 − γ + γ 2
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) , γ r + 1 2 − γ + γ r + 1 , γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) } . R_{\mathrm{gr}}(\gamma,r) \ge\max\left\{ \frac{\gamma}{r}, \frac{\gamma^{2}}{B_{\gamma}+\sqrt{\gamma(r-1)}}, \frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}, \frac{\gamma^{2}}{14\left(B_{\gamma}+\sqrt{\gamma(1-\gamma)(r-1)}\right)} \right\}. R gr ( γ , r ) ≥ max ⎩ ⎨ ⎧ r γ , B γ + γ ( r − 1 ) γ 2 , 2 − γ + γ r + 1 γ r + 1 , 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 ⎭ ⎬ ⎫ . and
R g r ( γ , r ) ≤ min { 1 2 , 20 max { γ r , γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) } } . R_{\mathrm{gr}}(\gamma,r) \le\min\left\{ \frac{1}{2},20\max\left\{ \frac{\gamma}{r},\frac{\gamma^{2}}{B_{\gamma}+\sqrt{\gamma(1-\gamma)(r-1)}} \right\} \right\}. R gr ( γ , r ) ≤ min { 2 1 , 20 max { r γ , B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 } } . Consequently,
R g r ( γ , r ) = Θ ( max { γ r , γ 2 1 + γ ( 1 − γ ) r } ) . (1) R_{\mathrm{gr}}(\gamma,r) = \Theta\left( \max\left\{ \frac{\gamma}{r}, \frac{\gamma^{2}}{1+\sqrt{\gamma(1-\gamma)r}} \right\} \right). \tag*{(1)} R gr ( γ , r ) = Θ ( max { r γ , 1 + γ ( 1 − γ ) r γ 2 } ) . (1) where the symbol Θ ( ⋅ ) \Theta(\cdot) Θ ( ⋅ )
Related Work
The notion of γ \gamma γ [5 , 6 ] , who proved that standard forward greedy achieves a ( 1 − e − γ ) (1-e^{-\gamma}) ( 1 − e − γ ) γ \gamma γ [2 ] refined this analysis by incorporating generalized curvature, while Harshaw et al. [13 ] showed that the ( 1 − e − γ ) (1-e^{-\gamma}) ( 1 − e − γ ) [27 ] further showed that the multi-objective evolutionary algorithm also can attain a ( 1 − e − γ ) (1-e^{-\gamma}) ( 1 − e − γ ) [7 ] subsequently introduced a broader class of γ \gamma γ α \alpha α
Moving beyond cardinality constraints, Chen et al. [4 ] proved that Residual Random Greedy achieves the rank-independent approximation factor ( 1 + 1 / γ ) − 2 (1+1/\gamma)^{-2} ( 1 + 1/ γ ) − 2 [29 ] then introduced the upper submodularity ratio β \beta β ( γ , β ) (\gamma,\beta) ( γ , β ) γ 2 ( 1 − e − ϕ ) / ϕ \gamma^2(1-e^{-\phi})/\phi γ 2 ( 1 − e − ϕ ) / ϕ ϕ ≜ γ 2 + β ( 1 − γ ) \phi\triangleq\gamma^2+\beta(1-\gamma) ϕ ≜ γ 2 + β ( 1 − γ ) [31 ] introduced a novel Multinoulli extension and its associated Multinoulli-SCG algorithm, which cam preserve the same approximation guarantee of [29 ] while requiring fewer function evaluations. Recently, [10 ] proposed a maximum-gain Poisson exchange algorithm that achieves a better approximation ratio arbitrarily close to 1 − ( γ / ( 2 − γ ) ) γ 2 / 2 ( 1 − γ ) 1-(\gamma/(2-\gamma))^{\gamma^2/2(1-\gamma)} 1 − ( γ / ( 2 − γ ) ) γ 2 /2 ( 1 − γ ) [11 , 12 , 19 , 26 ] explores a stronger weakly DR-submodular maximization problems.
Preliminaries
Notation. Let U U U f : 2 U → R + f:2^{U}\to\mathbb{R}_{+} f : 2 U → R + S ⊆ U S\subseteq U S ⊆ U e ∈ U e\in U e ∈ U S + e ≜ S ∪ { e } S+e\triangleq S\cup\{e\} S + e ≜ S ∪ { e } e e e S S S f ( e ∣ S ) ≜ f ( S + e ) − f ( S ) f(e\mid S)\triangleq f(S+e)-f(S) f ( e ∣ S ) ≜ f ( S + e ) − f ( S ) normalized if f ( ∅ ) = 0 f(\varnothing)=0 f ( ∅ ) = 0 monotone if f ( A ) ≤ f ( C ) f(A)\leq f(C) f ( A ) ≤ f ( C ) A ⊆ C ⊆ U A\subseteq C\subseteq U A ⊆ C ⊆ U normalized and monotone .
Weak Submodularity. For γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] f : 2 U → R + f:2^{U}\to\mathbb{R}_{+} f : 2 U → R + γ \gamma γ weakly submodular if, for every A ⊆ C ⊆ U A\subseteq C\subseteq U A ⊆ C ⊆ U
∑ e ∈ C ∖ A f ( e ∣ A ) ≥ γ ( f ( C ) − f ( A ) ) . (2) \sum_{e\in C\setminus A} f(e\mid A)\geq\gamma\bigl(f(C)-f(A)\bigr). \tag*{(2)} e ∈ C ∖ A ∑ f ( e ∣ A ) ≥ γ ( f ( C ) − f ( A ) ) . (2) Matroids. A matroid is a pair M ≜ ( U , I ) \mathcal{M}\triangleq(U,\mathcal{I}) M ≜ ( U , I ) U U U I ⊆ 2 U \mathcal{I}\subseteq2^{U} I ⊆ 2 U ∅ ∈ I \varnothing\in\mathcal{I} ∅ ∈ I C ∈ I C\in\mathcal{I} C ∈ I A ⊆ C A\subseteq C A ⊆ C A ∈ I A\in\mathcal{I} A ∈ I A , C ∈ I A,C\in\mathcal{I} A , C ∈ I ∣ A ∣ < ∣ C ∣ |A|<|C| ∣ A ∣ < ∣ C ∣ e ∈ C ∖ A e\in C\setminus A e ∈ C ∖ A A + e ∈ I A+e\in\mathcal{I} A + e ∈ I I \mathcal{I} I independent sets , and its maximal members are called bases . Every base has the same cardinality, called the rank of M \mathcal{M} M r r r
Standard Forward Greedy Method. Starting from S 0 = ∅ S_{0}=\varnothing S 0 = ∅ t = 1 , … , r t=1,\ldots,r t = 1 , … , r
s t ∈ arg max { f ( e ∣ S t − 1 ) : e ∉ S t − 1 , S t − 1 + e ∈ I } , S t = S t − 1 + s t . (3) s_{t}\in\arg\max\{f(e\mid S_{t-1}):e\notin S_{t-1},\ S_{t-1}+e\in\mathcal{I}\},\qquad S_{t}=S_{t-1}+s_{t}. \tag*{(3)} s t ∈ arg max { f ( e ∣ S t − 1 ) : e ∈ / S t − 1 , S t − 1 + e ∈ I } , S t = S t − 1 + s t . (3) After r r r S r S_r S r S r S_r S r γ \gamma γ f f f
R g r ( γ , r ) ≜ inf ( f , M ) f ( S r ) max T ∈ I f ( T ) (4) R_{\mathrm{gr}}(\gamma,r) \triangleq\inf_{(f,\mathcal{M})} \frac{f(S_r)}{\max_{T \in\mathcal{I}} f(T)} \tag*{(4)} R gr ( γ , r ) ≜ ( f , M ) inf max T ∈ I f ( T ) f ( S r ) (4) where the infimum is over all rank-r r r M \mathcal{M} M (3) . Note that we only consider instances with positive optimum.
Upper bounds for R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r )
To characterize upper bounds on R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r ) k k k N N N
U = G \mathbin{\mathaccent\cdot\cup} B \mathbin{\mathaccent\cdot\cup} E,\qquad G = \{g_1,\ldots,g_k\},\qquad B = \{b_1,\ldots,b_k\},\qquad E = \{e_1,\ldots,e_N\}.
Here, G G G good elements, B B B bad elements, and E E E k k k { b i , g i } \{b_i,g_i\} { b i , g i } N N N { e j } \{e_j\} { e j } r ≜ k + N r \triangleq k+N r ≜ k + N
The high-level idea is to design an objective function that forces the greedy algorithm to select all bad elements { b 1 , … , b k } \{b_1,\ldots,b_k\} { b 1 , … , b k } b i b_i b i g i g_i g i
To achieve this goal, we consider a simplified set objective function that depends only on the numbers of selected elements of each type. For a set S ⊆ U S \subseteq U S ⊆ U
b ( S ) = ∣ S ∩ B ∣ , q ( S ) = ∣ S ∩ G ∣ , s ( S ) = ∣ S ∩ E ∣ . b(S) = |S \cap B|,\qquad q(S) = |S \cap G|,\qquad s(S) = |S \cap E|. b ( S ) = ∣ S ∩ B ∣ , q ( S ) = ∣ S ∩ G ∣ , s ( S ) = ∣ S ∩ E ∣. Given a weight w > 0 w > 0 w > 0 H : Z + 2 → R + H:\mathbb{Z}_{+}^{2} \to\mathbb{R}_{+} H : Z + 2 → R +
f w , H ( S ) = w ⋅ b ( S ) + H ( q ( S ) , s ( S ) ) . (5) f_{w,H}(S) = w \cdot b(S) + H(q(S),s(S)). \tag*{(5)} f w , H ( S ) = w ⋅ b ( S ) + H ( q ( S ) , s ( S )) . (5) We next design H H H f w , H f_{w,H} f w , H γ \gamma γ
First core: a variant of the harmonic mean
Recall that the harmonic mean of two positive numbers x x x s s s
ϕ ( x , s ) = 2 x s x + s = 2 x − 1 + s − 1 . \phi(x,s) = \frac{2xs}{x+s} = \frac{2}{x^{-1}+s^{-1}}. ϕ ( x , s ) = x + s 2 x s = x − 1 + s − 1 2 . With the help of ϕ ( x , s ) \phi(x,s) ϕ ( x , s ) H ( q , s ) H(q,s) H ( q , s )
H ( q , s ) = 1 2 ϕ ( a ( q + λ ) , s ) = a ( q + λ ) s a ( q + λ ) + s , q , s ≥ 0. (6) H(q,s) = \frac{1}{2}\phi(a(q+\lambda),s) = \frac{a(q+\lambda)s}{a(q+\lambda)+s},\qquad q,s \ge0. \tag*{(6)} H ( q , s ) = 2 1 ϕ ( a ( q + λ ) , s ) = a ( q + λ ) + s a ( q + λ ) s , q , s ≥ 0. (6) where a ≥ 1 a \ge1 a ≥ 1 λ > 0 \lambda> 0 λ > 0 q q q s s s H ^ ( S ) = H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) \widehat{H}(S)=H(|S\cap G|,|S\cap E|) H ( S ) = H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) S ⊆ U S\subseteq U S ⊆ U H H H H ^ \widehat{H} H § 6 .
Lemma 3.1 (Continuous properties of the harmonic core). The function H H H (6) is nonnegative, coordinate-wise nondecreasing, and concave on R ≥ 0 2 \mathbb{R}_{\ge0}^2 R ≥ 0 2 x ≜ a ( q + λ ) x \triangleq a(q+\lambda) x ≜ a ( q + λ ) D ≜ x + s D \triangleq x+s D ≜ x + s
∂ q H ( q , s ) = a s 2 D 2 , H ( q + 1 , s ) − H ( q , s ) = D D + a ∂ q H ( q , s ) , (7) \partial_q H(q,s)=\frac{as^2}{D^2}, \qquad H(q+1,s)-H(q,s)=\frac{D}{D+a}\partial_q H(q,s), \tag*{(7)} ∂ q H ( q , s ) = D 2 a s 2 , H ( q + 1 , s ) − H ( q , s ) = D + a D ∂ q H ( q , s ) , (7) ∂ s H ( q , s ) = x 2 D 2 , H ( q , s + 1 ) − H ( q , s ) = D D + 1 ∂ s H ( q , s ) . (8) \partial_s H(q,s)=\frac{x^2}{D^2}, \qquad H(q,s+1)-H(q,s)=\frac{D}{D+1}\partial_s H(q,s). \tag*{(8)} ∂ s H ( q , s ) = D 2 x 2 , H ( q , s + 1 ) − H ( q , s ) = D + 1 D ∂ s H ( q , s ) . (8) Importantly, with the result of Lemma 3.1, we can prove that
Lemma 3.2. The set function H ^ ( S ) ≜ H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) \widehat{H}(S) \triangleq H\left(\lvert S \cap G\rvert,\lvert S \cap E\rvert\right) H ( S ) ≜ H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) γ λ \gamma_\lambda γ λ γ λ ≜ λ 1 + λ \gamma_\lambda\triangleq\frac{\lambda}{1+\lambda} γ λ ≜ 1 + λ λ
How the harmonic core misleads standard forward greedy?
Throughout this subsubsection, we assume N ≥ k N \ge k N ≥ k a = N / k ≥ 1 a=N/k \ge1 a = N / k ≥ 1 λ ≜ γ 1 − γ \lambda\triangleq\frac{\gamma}{1-\gamma} λ ≜ 1 − γ γ γ λ = λ / ( 1 + λ ) = γ \gamma_\lambda=\lambda/(1+\lambda)=\gamma γ λ = λ / ( 1 + λ ) = γ H ^ \widehat{H} H γ \gamma γ
f ( S ) = ∣ S ∩ B ∣ + H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) . (9) f(S)=\lvert S\cap B\rvert+H\left(\lvert S\cap G\rvert,\lvert S\cap E\rvert\right). \tag*{(9)} f ( S ) = ∣ S ∩ B ∣ + H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) . (9) is normalized, monotone, and γ \gamma γ
Whenever S S S S ⊆ B S\subseteq B S ⊆ B
f ( b i ∣ S ) = 1 , f ( g i ∣ S ) = 0 , f ( e ∣ S ) = a λ a λ + 1 < 1 , f(b_i\mid S)=1,\qquad f(g_i\mid S)=0,\qquad f(e\mid S)=\frac{a\lambda}{a\lambda+1}<1, f ( b i ∣ S ) = 1 , f ( g i ∣ S ) = 0 , f ( e ∣ S ) = aλ + 1 aλ < 1 , where b i ∉ S b_i\notin S b i ∈ / S k k k S r ≜ B ∪ E S_r\triangleq B\cup E S r ≜ B ∪ E G ∪ E G\cup E G ∪ E (9) and a = N / k a=N/k a = N / k
f ( S r ) ≜ k + λ N k + λ , f ( G ∪ E ) ≜ N ( k + λ ) 2 k + λ . (10) f(S_r)\triangleq k+\frac{\lambda N}{k+\lambda},\qquad f(G\cup E)\triangleq\frac{N(k+\lambda)}{2k+\lambda}. \tag*{(10)} f ( S r ) ≜ k + k + λ λ N , f ( G ∪ E ) ≜ 2 k + λ N ( k + λ ) . (10) Since O P T ≜ max T ∈ I f ( T ) ≥ f ( G ∪ E ) \mathrm{OPT}\triangleq\max_{T\in\mathcal{I}}f(T)\ge f(G\cup E) OPT ≜ max T ∈ I f ( T ) ≥ f ( G ∪ E ) R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r )
R g r ( γ , r ) ≤ f ( S r ) O P T ≤ 2 k + λ k + λ ( k N + λ k + λ ) ≤ 2 ( k N + λ k ) , (11) R_{\mathrm{gr}}(\gamma,r)\le\frac{f(S_r)}{\mathrm{OPT}}\le\frac{2k+\lambda}{k+\lambda}\left(\frac{k}{N}+\frac{\lambda}{k+\lambda}\right)\le2\left(\frac{k}{N}+\frac{\lambda}{k}\right), \tag*{(11)} R gr ( γ , r ) ≤ OPT f ( S r ) ≤ k + λ 2 k + λ ( N k + k + λ λ ) ≤ 2 ( N k + k λ ) , (11) where the final inequality comes from ( 2 k + λ ) / ( k + λ ) ≤ 2 (2k+\lambda)/(k+\lambda)\le2 ( 2 k + λ ) / ( k + λ ) ≤ 2 λ / ( k + λ ) ≤ λ / k \lambda/(k+\lambda)\le\lambda/k λ / ( k + λ ) ≤ λ / k R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r )
Proposition 3.3. For every 0 < γ < 1 0<\gamma<1 0 < γ < 1 r ≥ 2 r\ge2 r ≥ 2 λ ≜ γ / ( 1 − γ ) \lambda\triangleq\gamma/(1-\gamma) λ ≜ γ / ( 1 − γ )
R g r ( γ , r ) ≤ min 1 ≤ k ≤ ⌊ r / 2 ⌋ 2 k + λ k + λ ( k r − k + λ k + λ ) . (12) R_{\mathrm{gr}}(\gamma,r)\le\min_{1\le k\le\lfloor r/2\rfloor}\frac{2k+\lambda}{k+\lambda}\left(\frac{k}{r-k}+\frac{\lambda}{k+\lambda}\right). \tag*{(12)} R gr ( γ , r ) ≤ 1 ≤ k ≤ ⌊ r /2 ⌋ min k + λ 2 k + λ ( r − k k + k + λ λ ) . (12) Consequently, for every fixed γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 )
R g r ( γ , r ) ≤ 1 r max { 8 γ 1 − γ , 2 1 − γ γ } . (13) R_{\mathrm{gr}}(\gamma,r)\le\frac{1}{\sqrt{r}}\max\left\{8\sqrt{\frac{\gamma}{1-\gamma}},2\sqrt{\frac{1-\gamma}{\gamma}}\right\}. \tag*{(13)} R gr ( γ , r ) ≤ r 1 max { 8 1 − γ γ , 2 γ 1 − γ } . (13) The result of Proposition 3.3 immediately indicates an O γ ( r − 1 / 2 ) O_{\gamma}(r^{-1/2}) O γ ( r − 1/2 ) γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) γ ↓ 0 \gamma\downarrow0 γ ↓ 0 γ ↑ 1 \gamma\uparrow1 γ ↑ 1 max { 8 γ 1 − γ , 2 1 − γ γ } \max\left\{8\sqrt{\frac{\gamma}{1-\gamma}},2\sqrt{\frac{1-\gamma}{\gamma}}\right\} max { 8 1 − γ γ , 2 γ 1 − γ } uninformative .
Recall that standard forward greedy achieves the tight 1 / 2 1/2 1/2 [9 ] . Moreover, whenever 0 < γ 1 ≤ γ 2 ≤ 1 0 < \gamma_1 \le\gamma_2 \le1 0 < γ 1 ≤ γ 2 ≤ 1 γ 2 \gamma_2 γ 2 γ 1 \gamma_1 γ 1
R g r ( γ , r ) ≤ R g r ( 1 , r ) = 1 2 (14) R_{\mathrm{gr}}(\gamma,r) \le R_{\mathrm{gr}}(1,r) = \frac{1}{2} \tag*{(14)} R gr ( γ , r ) ≤ R gr ( 1 , r ) = 2 1 (14) for every γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ]
This universal 1 / 2 1/2 1/2 γ = 1 \gamma= 1 γ = 1 γ \gamma γ
Second core: a general power mean
As in the preceding subsection, we consider the same partition matroid constraint with a general power-mean core. For p ≥ 1 p \ge1 p ≥ 1
Ψ p ( x , s ) ≜ x s ( x p + s p ) 1 / p , x , s ≥ 0. (15) \Psi_p(x,s) \triangleq\frac{xs}{(x^p+s^p)^{1/p}}, \qquad x,s \ge0. \tag*{(15)} Ψ p ( x , s ) ≜ ( x p + s p ) 1/ p x s , x , s ≥ 0. (15) At the origin, we set Ψ p ( 0 , 0 ) : = 0 \Psi_p(0,0) := 0 Ψ p ( 0 , 0 ) := 0
Lemma 3.4 (Continuous properties of the power mean). The function Ψ p \Psi_p Ψ p is nonnegative, coordinate-wise nondecreasing, concave, and bounded above by min { x , s } \min\{x,s\} min { x , s } For x , s > 0 x,s > 0 x , s > 0
∂ x Ψ p ( x , s ) = s p + 1 ( x p + s p ) − 1 − 1 / p , ∂ s Ψ p ( x , s ) = x p + 1 ( x p + s p ) − 1 − 1 / p . \partial_x\Psi_p(x,s) = s^{p+1}(x^p+s^p)^{-1-1/p}, \qquad\partial_s\Psi_p(x,s) = x^{p+1}(x^p+s^p)^{-1-1/p}. ∂ x Ψ p ( x , s ) = s p + 1 ( x p + s p ) − 1 − 1/ p , ∂ s Ψ p ( x , s ) = x p + 1 ( x p + s p ) − 1 − 1/ p . Moreover, the right derivative ∂ s + Ψ p ( x , 0 ) \partial_s^+\Psi_p(x,0) ∂ s + Ψ p ( x , 0 ) equals one for every x > 0 x > 0 x > 0
We next investigate a set objective induced by the aforementioned core of the power mean. Specifically, for a ≥ 1 a \ge1 a ≥ 1
Ψ ^ a , p ( S ) = Ψ p ( a ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) , S ⊆ U , \widehat{\Psi}_{a,p}(S) = \Psi_p\left(a|S \cap G|, |S \cap E|\right), \qquad S \subseteq U, Ψ a , p ( S ) = Ψ p ( a ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) , S ⊆ U , where G G G good elements and E E E auxiliary set. Subsequently, we establish the weak submodularity of Ψ ^ a , p \widehat{\Psi}_{a,p} Ψ a , p
Lemma 3.5. For every inclusion A ⊆ C ⊆ U A \subseteq C \subseteq U A ⊆ C ⊆ U with ∣ A ∩ G ∣ ≥ 1 |A \cap G| \ge1 ∣ A ∩ G ∣ ≥ 1
∑ e ∈ C ∖ A ( Ψ ^ a , p ( A + e ) − Ψ ^ a , p ( A ) ) ≥ c p ( Ψ ^ a , p ( C ) − Ψ ^ a , p ( A ) ) , (16) \sum_{e \in C \setminus A}\left(\widehat{\Psi}_{a,p}(A+e)-\widehat{\Psi}_{a,p}(A)\right) \ge c_p\left(\widehat{\Psi}_{a,p}(C)-\widehat{\Psi}_{a,p}(A)\right), \tag*{(16)} e ∈ C ∖ A ∑ ( Ψ a , p ( A + e ) − Ψ a , p ( A ) ) ≥ c p ( Ψ a , p ( C ) − Ψ a , p ( A ) ) , (16) where c p ≜ ( 1 − 2 − p ) / p c_p \triangleq(1-2^{-p})/p c p ≜ ( 1 − 2 − p ) / p
Next, we consider the following special parameterization:
γ ≜ τ ( 1 + τ ) ( 1 + τ p ) 1 / p , (17) \gamma\triangleq\frac{\tau}{(1+\tau)(1+\tau^p)^{1/p}}, \tag*{(17)} γ ≜ ( 1 + τ ) ( 1 + τ p ) 1/ p τ , (17) where τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] 0 < γ ≤ min { c p , 2 − 1 − 1 / p } 0 < \gamma\le\min\{c_p,2^{-1-1/p}\} 0 < γ ≤ min { c p , 2 − 1 − 1/ p } (17) , viewed as a function of τ \tau τ 2 − 1 − 1 / p 2^{-1-1/p} 2 − 1 − 1/ p
Thus, such a suitable τ \tau τ k ≥ 1 k \ge1 k ≥ 1 a = k / τ ≥ 1 a = k/\tau\ge1 a = k / τ ≥ 1
H p , τ , k ( q , s ) = { min { s , k } , q = 0 , γ − 1 Ψ p ( a q , s ) , q ≥ 1. (18) H_{p,\tau,k}(q,s) =
\begin{cases}
\min\{s,k\}, & q=0,\\
\gamma^{-1}\Psi_p(aq,s), & q\ge1.
\end{cases} \tag*{(18)} H p , τ , k ( q , s ) = { min { s , k } , γ − 1 Ψ p ( a q , s ) , q = 0 , q ≥ 1. (18) From Eq. (18) , we know this core H p , τ , k H_{p,\tau,k} H p , τ , k Ψ p \Psi_p Ψ p min { s , k } \min\{s,k\} min { s , k } H p , τ , k H_{p,\tau,k} H p , τ , k
Lemma 3.6. Under Eq. (17) and 0 < γ ≤ min { c p , 2 − 1 − 1 / p } 0 < \gamma\le\min\{c_p,2^{-1-1/p}\} 0 < γ ≤ min { c p , 2 − 1 − 1/ p } we define
H ^ p , τ , k ( S ) = H p , τ , k ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) , S ⊆ U . \widehat{H}_{p,\tau,k}(S) = H_{p,\tau,k}(|S \cap G|,|S \cap E|), \qquad S \subseteq U. H p , τ , k ( S ) = H p , τ , k ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) , S ⊆ U . Then H ^ p , τ , k \widehat{H}_{p,\tau,k} H p , τ , k is normalized, monotone, and globally γ \gamma γ weakly submodular.
Sharpening the joint dependence with the power core
As in the first-core construction, we use the partition matroid introduced at the beginning of Section 3 and assume N ≥ k N \ge k N ≥ k (5) with w ≜ 1 + ε w \triangleq1+\varepsilon w ≜ 1 + ε H p , τ , k H_{p,\tau,k} H p , τ , k
f ( S ) = ( 1 + ε ) ⋅ ∣ S ∩ B ∣ + H p , τ , k ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) , ε > 0. (19) f(S)=(1+\varepsilon)\cdot|S\cap B|+H_{p,\tau,k}(|S\cap G|,|S\cap E|), \qquad\varepsilon>0. \tag*{(19)} f ( S ) = ( 1 + ε ) ⋅ ∣ S ∩ B ∣ + H p , τ , k ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) , ε > 0. (19) Here, γ = τ ( 1 + τ ) ( 1 + τ p ) 1 / p \gamma=\frac{\tau}{(1+\tau)(1+\tau^p)^{1/p}} γ = ( 1 + τ ) ( 1 + τ p ) 1/ p τ 0 < γ ≤ min { c p , 2 − 1 − 1 / p } 0<\gamma\le\min\{c_p,2^{-1-1/p}\} 0 < γ ≤ min { c p , 2 − 1 − 1/ p } H p , τ , k H_{p,\tau,k} H p , τ , k γ \gamma γ f f f (19) is also monotone γ \gamma γ S S S S ⊆ B S\subseteq B S ⊆ B
f ( b i ∣ S ) = 1 + ε , f ( g i ∣ S ) = 0 , f ( e j ∣ S ) = 1. f(b_i\mid S)=1+\varepsilon,\qquad f(g_i\mid S)=0,\qquad f(e_j\mid S)=1. f ( b i ∣ S ) = 1 + ε , f ( g i ∣ S ) = 0 , f ( e j ∣ S ) = 1. Thus the greedy method strictly chooses all k k k k k k N N N S r ≜ B ∪ E S_r\triangleq B\cup E S r ≜ B ∪ E N ≥ k N\ge k N ≥ k b ( B ∪ E ) = k b(B\cup E)=k b ( B ∪ E ) = k q ( B ∪ E ) = 0 q(B\cup E)=0 q ( B ∪ E ) = 0 s ( B ∪ E ) = N s(B\cup E)=N s ( B ∪ E ) = N
f ( S r ) = f ( B ∪ E ) = ( 2 + ε ) k . (20) f(S_r)=f(B\cup E)=(2+\varepsilon)k. \tag*{(20)} f ( S r ) = f ( B ∪ E ) = ( 2 + ε ) k . (20) Moreover, the base G ∪ E G\cup E G ∪ E a = k / τ a=k/\tau a = k / τ
f ( G ∪ E ) = k 2 N γ ( k 2 p + τ p N p ) 1 / p . (21) f(G\cup E)=\frac{k^2N}{\gamma\left(k^{2p}+\tau^pN^p\right)^{1/p}}. \tag*{(21)} f ( G ∪ E ) = γ ( k 2 p + τ p N p ) 1/ p k 2 N . (21) Comparing these two bases and letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0
R g r ( γ , k + N ) ≤ f ( S r ) f ( G ∪ E ) ≤ 2 γ [ ( k N ) p + ( τ k ) p ] 1 / p . (22) R_{\mathrm{gr}}(\gamma,k+N)\le\frac{f(S_r)}{f(G\cup E)}
\le2\gamma\left[\left(\frac{k}{N}\right)^p+\left(\frac{\tau}{k}\right)^p\right]^{1/p}. \tag*{(22)} R gr ( γ , k + N ) ≤ f ( G ∪ E ) f ( S r ) ≤ 2 γ [ ( N k ) p + ( k τ ) p ] 1/ p . (22) As a result, from r ≜ N + k r\triangleq N+k r ≜ N + k N ≥ k N\ge k N ≥ k
Proposition 3.7. For every p ≥ 1 p \ge1 p ≥ 1 0 < γ ≤ min { c p , 2 − 1 − 1 / p } 0 < \gamma\le\min\{c_p,2^{-1-1/p}\} 0 < γ ≤ min { c p , 2 − 1 − 1/ p } τ ∈ ( 0 , 1 ] \tau\in(0,1] τ ∈ ( 0 , 1 ] (17) . Then, for every r ≥ 2 r \ge2 r ≥ 2
R g r ( γ , r ) ≤ min 1 ≤ k ≤ ⌊ r / 2 ⌋ 2 γ [ ( k r − k ) p + ( τ k ) p ] 1 / p . (23) R_{\mathrm{gr}}(\gamma,r) \le\min_{1 \le k \le\lfloor r/2 \rfloor} 2\gamma\left[\left(\frac{k}{r-k}\right)^p+\left(\frac{\tau}{k}\right)^p\right]^{1/p}. \tag*{(23)} R gr ( γ , r ) ≤ 1 ≤ k ≤ ⌊ r /2 ⌋ min 2 γ [ ( r − k k ) p + ( k τ ) p ] 1/ p . (23) The main advantage of Proposition 3.7 mainly lies in how the weak submodularity ratio enters the resulting bound. Note that In Eq. (23) , γ \gamma γ R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r ) γ \gamma γ
A uniform upper bound
The preceding subsections develop two complementary upper-bound constructions. More specifically, Proposition 3.7 uses the power core to recover the dependence on γ \gamma γ γ ↓ 0 \gamma\downarrow0 γ ↓ 0 γ \gamma γ Proposition 3.3 yields the required O γ ( r − 1 / 2 ) O_\gamma(r^{-1/2}) O γ ( r − 1/2 ) 1 / 2 1/2 1/2
Theorem 3.8. For every 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 r ≥ 2 r \ge2 r ≥ 2
R g r ( γ , r ) ≤ min { 1 2 , 20 max { γ r , γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) } } . (24) R_{\mathrm{gr}}(\gamma,r) \le\min\left\{\frac{1}{2},20\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\right\}\right\}. \tag*{(24)} R gr ( γ , r ) ≤ min { 2 1 , 20 max { r γ , B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 } } . (24) where B γ ≜ 2 − γ + γ 2 B_\gamma\triangleq2-\gamma+\gamma^2 B γ ≜ 2 − γ + γ 2
Lower bounds for R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r )
In this section, we suppose that O ∈ I O \in\mathcal{I} O ∈ I f ( O ) ≜ max T ∈ I f ( T ) f(O) \triangleq\max_{T\in\mathcal{I}}f(T) f ( O ) ≜ max T ∈ I f ( T ) O P T ≜ f ( O ) \mathrm{OPT} \triangleq f(O) OPT ≜ f ( O ) S 0 , S 1 , … , S r S_0,S_1,\ldots,S_r S 0 , S 1 , … , S r
F t ≜ f ( S t ) , d t ≜ F t − F t − 1 , W t ≜ ∑ i = 1 t i d i , K t ≜ ∑ j = 0 t − 1 F j . F_t \triangleq f(S_t), \qquad d_t \triangleq F_t-F_{t-1}, \qquad W_t \triangleq\sum_{i=1}^{t} i d_i, \qquad K_t \triangleq\sum_{j=0}^{t-1} F_j. F t ≜ f ( S t ) , d t ≜ F t − F t − 1 , W t ≜ i = 1 ∑ t i d i , K t ≜ j = 0 ∑ t − 1 F j . We now turn to lower bounds for R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r ) γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] r r r γ \gamma γ § 7 .
A universal rank-dependent guarantee
In this subsection, we begin with several lemmas that will be frequently used in the lower-bound analysis of R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r ) F t F_t F t W t W_t W t K t K_t K t
Lemma 4.1 (Basic identities). For every 1 ≤ t ≤ r 1 \le t \le r 1 ≤ t ≤ r
d t ≥ 0 d_t \ge0 d t ≥ 0
W t = t F t − K t W_t=tF_t-K_t W t = t F t − K t W t ≥ F t W_t \ge F_t W t ≥ F t
The next lemma orders the elements of O O O S t S_t S t O O O
Lemma 4.2. The optimal base can be ordered as O = { o 1 , … , o r } O = \{o_1,\ldots,o_r\} O = { o 1 , … , o r } t = 0 , … , r − 1 t = 0,\ldots,r-1 t = 0 , … , r − 1
S t ∪ { o t + 1 , … , o r } S_t \cup\{o_{t+1},\ldots,o_r\} S t ∪ { o t + 1 , … , o r } is a base. In particular, o i o_i o i S i − 1 S_{i-1} S i − 1 o j o_j o j S t S_t S t j > t j > t j > t
With this result of Lemma 4.2 and γ \gamma γ
Lemma 4.3. For $1 \le i \le t \le r$,
γ f ( o i ∣ S t ) ≤ ( t − i + 2 ) d i − γ ( F t − F i − 1 ) . (25) \gamma f(o_i \mid S_t) \le(t-i+2)d_i-\gamma(F_t-F_{i-1}). \tag*{(25)} γ f ( o i ∣ S t ) ≤ ( t − i + 2 ) d i − γ ( F t − F i − 1 ) . (25) By summing Eq. (25) , we also can have
Lemma 4.4. Let B γ ≜ 2 − γ + γ 2 B_\gamma\triangleq2-\gamma+\gamma^2 B γ ≜ 2 − γ + γ 2 0 ≤ t ≤ r 0 \le t \le r 0 ≤ t ≤ r
γ 2 O P T ≤ B γ F t + K t + γ ( r − t ) d t + 1 . (26) \gamma^2\mathrm{OPT} \le B_\gamma F_t+K_t+\gamma(r-t)d_{t+1}. \tag*{(26)} γ 2 OPT ≤ B γ F t + K t + γ ( r − t ) d t + 1 . (26) Particularly when t = r t=r t = r
γ 2 O P T ≤ B γ F r + K r . (27) \gamma^2\mathrm{OPT} \le B_\gamma F_r+K_r. \tag*{(27)} γ 2 OPT ≤ B γ F r + K r . (27) To use the relations in Eq. (26) and Eq. (27) , we first establish the following recursive inequality:
Lemma 4.5 (Recurrence aggregation). Let r ≥ 1 r \ge1 r ≥ 1 A , B , C ≥ 0 A,B,C \ge0 A , B , C ≥ 0 0 = F 0 ≤ F 1 ≤ ⋯ ≤ F r = M 0=F_0 \le F_1 \le\cdots\le F_r=M 0 = F 0 ≤ F 1 ≤ ⋯ ≤ F r = M K t = ∑ j < t F j K_t=\sum_{j<t}F_j K t = ∑ j < t F j
C ≤ A ( F t + 1 − F t ) + B F t + K t ( t < r ) , C ≤ B M + K r . C \le A(F_{t+1}-F_t)+BF_t+K_t \quad(t<r), \qquad C \le BM+K_r. C ≤ A ( F t + 1 − F t ) + B F t + K t ( t < r ) , C ≤ B M + K r . Then
C ≤ ( B + A ( 1 − 1 / r ) ) M . (28) C \le\left(B+\sqrt{A(1-1/r)}\right)M. \tag*{(28)} C ≤ ( B + A ( 1 − 1/ r ) ) M . (28) According to this Lemma 4.5 and the results of Lemma 4.3 , we can prove
Theorem 4.6. For every 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1 r ≥ 2 r\ge2 r ≥ 2 B γ ≜ 2 − γ + γ 2 B_\gamma\triangleq2-\gamma+\gamma^2 B γ ≜ 2 − γ + γ 2
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) } . (29) R_{\mathrm{gr}}(\gamma,r)\ge\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}}\right\}. \tag*{(29)} R gr ( γ , r ) ≥ max { r γ , B γ + γ ( r − 1 ) γ 2 } . (29) It is worth noting that, as γ → 1 \gamma\to1 γ → 1 (29) will converge to
max { 1 r , 1 2 + r − 1 } . \max\left\{\frac{1}{r},\frac{1}{2+\sqrt{r-1}}\right\}. max { r 1 , 2 + r − 1 1 } . For r ≥ 3 r\ge3 r ≥ 3 strictly weaker than the classical 1/2-approximation guarantee for monotone submodular maximization [9 ] . A natural question is whether this gap can be closed when γ = 1 \gamma=1 γ = 1
Theorem 4.7. For every 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1 r ≥ 1 r\ge1 r ≥ 1
R g r ( γ , r ) ≥ γ r + 1 2 − γ + γ r + 1 . (30) R_{\mathrm{gr}}(\gamma,r)\ge\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}. \tag*{(30)} R gr ( γ , r ) ≥ 2 − γ + γ r + 1 γ r + 1 . (30) Note that lim γ ↑ 1 γ r + 1 2 − γ + γ r + 1 = 1 2 \lim_{\gamma\uparrow1}\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}=\frac{1}{2} lim γ ↑ 1 2 − γ + γ r + 1 γ r + 1 = 2 1 Theorem 4.6 and Theorem 4.7 , we can obtain that, for every 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 r ≥ 2 r\geq2 r ≥ 2
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) , γ r + 1 2 − γ + γ r + 1 } . (31) R_{\mathrm{gr}}(\gamma,r)\geq\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}},\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}\right\}. \tag*{(31)} R gr ( γ , r ) ≥ max { r γ , B γ + γ ( r − 1 ) γ 2 , 2 − γ + γ r + 1 γ r + 1 } . (31) where B γ ≜ 2 − γ + γ 2 B_\gamma\triangleq2-\gamma+\gamma^2 B γ ≜ 2 − γ + γ 2 (31) with the two lower guarantees from the analysis of [11 ] .
Lemma 4.8 (Comparison with previous lower bounds). For every 0 < γ ≤ 1 0<\gamma\leq1 0 < γ ≤ 1 r ≥ 2 r\geq2 r ≥ 2
R g r ( γ , r ) ≥ γ 2 B γ + γ ( r − 1 ) > γ 2 2 + 2 γ r + γ 2 > 0.4 γ 2 1 + γ r . (32) R_{\mathrm{gr}}(\gamma,r)\geq\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}}>\frac{\gamma^2}{2+2\sqrt{\gamma r}+\gamma^2}>\frac{0.4\gamma^2}{1+\sqrt{\gamma r}}. \tag*{(32)} R gr ( γ , r ) ≥ B γ + γ ( r − 1 ) γ 2 > 2 + 2 γ r + γ 2 γ 2 > 1 + γ r 0.4 γ 2 . (32) Thus, for r ≥ 2 r\geq2 r ≥ 2 (31) strictly improves the earlier result in [11 ] .
A Refined lower-bound analysis for γ ∈ [ 1 / 2 , 1 ) \gamma\in[1/2,1) γ ∈ [ 1/2 , 1 )
Recall that Theorem 4.6 gives
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) } . R_{\mathrm{gr}}(\gamma,r)\geq\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}}\right\}. R gr ( γ , r ) ≥ max { r γ , B γ + γ ( r − 1 ) γ 2 } . whereas the upper bound in Theorem 3.8 is governed by
Φ ( γ , r ) ≜ max { γ r , γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) } . \Phi(\gamma,r)\triangleq\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\right\}. Φ ( γ , r ) ≜ max { r γ , B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 } . When 0 < γ ≤ 1 / 2 0<\gamma\leq1/2 0 < γ ≤ 1/2 1 − γ ≥ 1 / 2 1-\gamma\geq1/2 1 − γ ≥ 1/2 γ ( r − 1 ) ≤ 2 γ ( 1 − γ ) ( r − 1 ) \sqrt{\gamma(r-1)}\leq\sqrt{2\gamma(1-\gamma)(r-1)} γ ( r − 1 ) ≤ 2 γ ( 1 − γ ) ( r − 1 )
R g r ( γ , r ) ≥ max { γ r , γ 2 2 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) } . R_{\mathrm{gr}}(\gamma,r)\geq\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{\sqrt{2}\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}\right\}. R gr ( γ , r ) ≥ max ⎩ ⎨ ⎧ r γ , 2 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 ⎭ ⎬ ⎫ . As a result, over this range 0 < γ ≤ 1 / 2 0<\gamma\leq1/2 0 < γ ≤ 1/2 Theorem 4.6 captures the same asymptotic dependence on γ \gamma γ r r r Theorem 3.8 .
However, this relationship breaks down as γ ↑ 1 \gamma\uparrow1 γ ↑ 1 γ ( r − 1 ) \sqrt{\gamma(r-1)} γ ( r − 1 ) γ ( 1 − γ ) ( r − 1 ) \sqrt{\gamma(1-\gamma)(r-1)} γ ( 1 − γ ) ( r − 1 ) γ ∈ [ 1 / 2 , 1 ) \gamma\in[1/2,1) γ ∈ [ 1/2 , 1 ) 1 − γ 1-\gamma 1 − γ
Before going into the details, like Lemma 4.4 we first present a sharper upper bound on OPT for the regime where γ \gamma γ
Lemma 4.9. For 1 / 2 ≤ γ < 1 1/2\leq\gamma<1 1/2 ≤ γ < 1 0 ≤ t < r 0\leq t<r 0 ≤ t < r D γ ≜ 60 − 15 γ + γ 2 D_\gamma\triangleq60-15\gamma+\gamma^2 D γ ≜ 60 − 15 γ + γ 2
γ 2 O P T ≤ D γ F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 . (33) \gamma^2\mathrm{OPT}\leq D_\gamma F_t+15(1-\gamma)K_t+\gamma(r-t)d_{t+1}. \tag*{(33)} γ 2 OPT ≤ D γ F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 . (33) In particular,
γ 2 O P T ≤ D γ F r + 15 ( 1 − γ ) K r . (34) \gamma^2\mathrm{OPT}\leq D_\gamma F_r+15(1-\gamma)K_r. \tag*{(34)} γ 2 OPT ≤ D γ F r + 15 ( 1 − γ ) K r . (34) Recall that Lemma 4.4 gives the result γ 2 O P T ≤ B γ F t + K t + γ ( r − t ) d t + 1 \gamma^{2}\mathrm{OPT} \le B_{\gamma}F_{t} + K_{t} + \gamma(r-t)d_{t+1} γ 2 OPT ≤ B γ F t + K t + γ ( r − t ) d t + 1 Lemma 4.9 replaces the coefficient of the accumulated history K t K_{t} K t 15 ( 1 − γ ) 15(1-\gamma) 15 ( 1 − γ ) (33) and Eq. (34) can produce a better dependence of order γ ( 1 − γ ) ( r − 1 ) \sqrt{\gamma(1-\gamma)(r-1)} γ ( 1 − γ ) ( r − 1 )
Theorem 4.10. For every 1 / 2 ≤ γ < 1 1/2 \le\gamma< 1 1/2 ≤ γ < 1 r ≥ 2 r \ge2 r ≥ 2 D γ ≜ 60 − 15 γ + γ 2 D_{\gamma} \triangleq60 - 15\gamma+ \gamma^{2} D γ ≜ 60 − 15 γ + γ 2
R g r ( γ , r ) ≥ max { γ r , γ 2 D γ + 15 γ ( 1 − γ ) ( r − 1 ) } . (35) R_{\mathrm{gr}}(\gamma,r) \ge\max\left\{\frac{\gamma}{r},\frac{\gamma^{2}}{D_{\gamma}+\sqrt{15\gamma(1-\gamma)(r-1)}}\right\}. \tag*{(35)} R gr ( γ , r ) ≥ max { r γ , D γ + 15 γ ( 1 − γ ) ( r − 1 ) γ 2 } . (35) Merging the result of Theorem 4.10 into the aforementioned Eq. (31) , we can finally obtain a uniform lower bound for R g r ( γ , r ) R_{\mathrm{gr}}(\gamma,r) R gr ( γ , r )
Theorem 4.11. For every 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 r ≥ 2 r \ge2 r ≥ 2
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) , γ r + 1 2 − γ + γ r + 1 , γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) } . (36) R_{\mathrm{gr}}(\gamma,r) \ge\max\left\{\frac{\gamma}{r},\frac{\gamma^{2}}{B_{\gamma}+\sqrt{\gamma(r-1)}},\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}},\frac{\gamma^{2}}{14\left(B_{\gamma}+\sqrt{\gamma(1-\gamma)(r-1)}\right)}\right\}. \tag*{(36)} R gr ( γ , r ) ≥ max ⎩ ⎨ ⎧ r γ , B γ + γ ( r − 1 ) γ 2 , 2 − γ + γ r + 1 γ r + 1 , 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 ⎭ ⎬ ⎫ . (36) where B γ ≜ 2 − γ + γ 2 B_{\gamma} \triangleq2-\gamma+\gamma^{2} B γ ≜ 2 − γ + γ 2
Conclusion
In this paper, we provide an asymptotically tight characterization of the worst-case performance of standard forward greedy for matroid-constrained weakly submodular maximization. Specifically, for every submodularity ratio γ ∈ ( 0 , 1 ] \gamma\in(0,1] γ ∈ ( 0 , 1 ] r ≥ 2 r \ge2 r ≥ 2
R g r ( γ , r ) = Θ ( max { γ r , γ 2 1 + γ ( 1 − γ ) r } ) . R_{\mathrm{gr}}(\gamma,r)=\Theta\left(\max\left\{\frac{\gamma}{r},\frac{\gamma^{2}}{1+\sqrt{\gamma(1-\gamma)r}}\right\}\right). R gr ( γ , r ) = Θ ( max { r γ , 1 + γ ( 1 − γ ) r γ 2 } ) . This characterization reveals how the performance of standard greedy varies across different γ \gamma γ r r r γ → 0 \gamma\to0 γ → 0 γ r = O ( 1 ) \gamma r = O(1) γ r = O ( 1 ) R g r ( γ , r ) = Θ ( γ / r ) R_{\mathrm{gr}}(\gamma,r)=\Theta(\gamma/r) R gr ( γ , r ) = Θ ( γ / r ) γ → 0 \gamma\to0 γ → 0 γ r → ∞ \gamma r \to\infty γ r → ∞ R g r ( γ , r ) = Θ ( γ 3 / 2 / r ) R_{\mathrm{gr}}(\gamma,r)=\Theta(\gamma^{3/2}/\sqrt{r}) R gr ( γ , r ) = Θ ( γ 3/2 / r ) γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) R g r ( γ , r ) = Θ γ ( r − 1 / 2 ) R_{\mathrm{gr}}(\gamma,r)=\Theta_{\gamma}(r^{-1/2}) R gr ( γ , r ) = Θ γ ( r − 1/2 ) γ \gamma γ r − 1 / 2 r^{-1/2} r − 1/2
Proofs for the upper bounds
Proof of Lemma 3.1
Proof. For the harmonic mean ϕ ( x , s ) = 2 x s / ( x + s ) \phi(x,s) = 2xs/(x+s) ϕ ( x , s ) = 2 x s / ( x + s )
∇ 2 ϕ ( x , s ) = − 4 ( x + s ) 3 ( s 2 − x s − x s x 2 ) ⪯ 0. \nabla^{2}\phi(x,s) = -\frac{4}{(x+s)^{3}}\begin{pmatrix} s^{2} & -xs \\ -xs & x^{2} \end{pmatrix} \preceq0. ∇ 2 ϕ ( x , s ) = − ( x + s ) 3 4 ( s 2 − x s − x s x 2 ) ⪯ 0. As a result, ϕ ( x , s ) \phi(x,s) ϕ ( x , s ) H ( q , s ) = 1 2 ϕ ( a ( q + λ ) , s ) H(q,s) = \frac{1}{2}\phi(a(q+\lambda),s) H ( q , s ) = 2 1 ϕ ( a ( q + λ ) , s )
∂ q H ( q , s ) = a s 2 D 2 , ∂ s H ( q , s ) = x 2 D 2 . \partial_{q}H(q,s) = \frac{as^{2}}{D^{2}}, \qquad\partial_{s}H(q,s) = \frac{x^{2}}{D^{2}}. ∂ q H ( q , s ) = D 2 a s 2 , ∂ s H ( q , s ) = D 2 x 2 . where x ≜ a ( q + λ ) x \triangleq a(q+\lambda) x ≜ a ( q + λ ) D ≜ x + s D \triangleq x+s D ≜ x + s H ( q , s ) H(q,s) H ( q , s ) H ( q , s ) H(q,s) H ( q , s )
H ( q + 1 , s ) − H ( q , s ) = a s 2 D ( D + a ) = D D + a ∂ q H ( q , s ) , H(q+1,s)-H(q,s)=\frac{as^{2}}{D(D+a)}=\frac{D}{D+a}\partial_q H(q,s), H ( q + 1 , s ) − H ( q , s ) = D ( D + a ) a s 2 = D + a D ∂ q H ( q , s ) , H ( q , s + 1 ) − H ( q , s ) = x 2 D ( D + 1 ) = D D + 1 ∂ s H ( q , s ) , H(q,s+1)-H(q,s)=\frac{x^{2}}{D(D+1)}=\frac{D}{D+1}\partial_s H(q,s), H ( q , s + 1 ) − H ( q , s ) = D ( D + 1 ) x 2 = D + 1 D ∂ s H ( q , s ) , which proves the claimed identities in Lemma 3.1 .
Proof of Lemma 3.2
Proof. Normalization follows from H ^ ( ∅ ) = H ( 0 , 0 ) = 1 2 ϕ ( a λ , 0 ) = 0 \widehat{H}(\varnothing)=H(0,0)=\frac{1}{2}\phi(a\lambda,0)=0 H ( ∅ ) = H ( 0 , 0 ) = 2 1 ϕ ( aλ , 0 ) = 0 Lemma 3.1 , we know that H H H H ^ ( S ) ≜ H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) \widehat{H}(S) \triangleq H(|S\cap G|,|S\cap E|) H ( S ) ≜ H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) A ⊆ C ⊆ U A\subseteq C\subseteq U A ⊆ C ⊆ U
q = ∣ A ∩ G ∣ , s = ∣ A ∩ E ∣ , u = ∣ ( C ∖ A ) ∩ G ∣ , v = ∣ ( C ∖ A ) ∩ E ∣ . q=|A\cap G|,\quad s=|A\cap E|,\quad u=|(C\setminus A)\cap G|,\quad v=|(C\setminus A)\cap E|. q = ∣ A ∩ G ∣ , s = ∣ A ∩ E ∣ , u = ∣ ( C ∖ A ) ∩ G ∣ , v = ∣ ( C ∖ A ) ∩ E ∣. Elements of B B B H ^ \widehat{H} H
∑ e ∈ C ∖ A H ^ ( e ∣ A ) = u ( H ( q + 1 , s ) − H ( q , s ) ) + v ( H ( q , s + 1 ) − H ( q , s ) ) . (37) \sum_{e\in C\setminus A}\widehat{H}(e\mid A)=u\bigl(H(q+1,s)-H(q,s)\bigr)+v\bigl(H(q,s+1)-H(q,s)\bigr). \tag*{(37)} e ∈ C ∖ A ∑ H ( e ∣ A ) = u ( H ( q + 1 , s ) − H ( q , s ) ) + v ( H ( q , s + 1 ) − H ( q , s ) ) . (37) With D ≜ a ( q + λ ) + s D\triangleq a(q+\lambda)+s D ≜ a ( q + λ ) + s a ≥ 1 a\geq1 a ≥ 1 D ≥ a λ D\geq a\lambda D ≥ aλ
D D + a ≥ λ 1 + λ , D D + 1 ≥ λ 1 + λ . \frac{D}{D+a}\geq\frac{\lambda}{1+\lambda},\qquad\frac{D}{D+1}\geq\frac{\lambda}{1+\lambda}. D + a D ≥ 1 + λ λ , D + 1 D ≥ 1 + λ λ . Together with Lemma 3.1 and γ λ ≜ λ 1 + λ \gamma_\lambda\triangleq\frac{\lambda}{1+\lambda} γ λ ≜ 1 + λ λ
H ( q + 1 , s ) − H ( q , s ) ≥ γ λ ⋅ ∂ q H ( q , s ) , H(q+1,s)-H(q,s)\geq\gamma_\lambda\cdot\partial_q H(q,s), H ( q + 1 , s ) − H ( q , s ) ≥ γ λ ⋅ ∂ q H ( q , s ) , H ( q , s + 1 ) − H ( q , s ) ≥ γ λ ⋅ ∂ s H ( q , s ) . H(q,s+1)-H(q,s)\geq\gamma_\lambda\cdot\partial_s H(q,s). H ( q , s + 1 ) − H ( q , s ) ≥ γ λ ⋅ ∂ s H ( q , s ) . Using Eq. (37) and then the concavity of H H H
∑ e ∈ C ∖ A H ^ ( e ∣ A ) ≥ γ λ ( u ∂ q H ( q , s ) + v ∂ s H ( q , s ) ) ≥ γ λ ( H ( q + u , s + v ) − H ( q , s ) ) = γ λ ( H ^ ( C ) − H ^ ( A ) ) . \begin{aligned}
\sum_{e\in C\setminus A}\widehat{H}(e\mid A)\geq\gamma_\lambda\bigl(u\partial_q H(q,s)+v\partial_s H(q,s)\bigr) \\
&\geq\gamma_\lambda\bigl(H(q+u,s+v)-H(q,s)\bigr) \\
&=\gamma_\lambda\bigl(\widehat{H}(C)-\widehat{H}(A)\bigr).
\end{aligned} e ∈ C ∖ A ∑ H ( e ∣ A ) ≥ γ λ ( u ∂ q H ( q , s ) + v ∂ s H ( q , s ) ) ≥ γ λ ( H ( q + u , s + v ) − H ( q , s ) ) = γ λ ( H ( C ) − H ( A ) ) . So H ^ ( S ) ≜ H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) \widehat{H}(S)\triangleq H(|S\cap G|,|S\cap E|) H ( S ) ≜ H ( ∣ S ∩ G ∣ , ∣ S ∩ E ∣ ) γ λ \gamma_\lambda γ λ
Proof of Proposition 3.3
Proof. Note that in Section 3.1.1, we assume N = r − k ≥ k N=r-k\geq k N = r − k ≥ k 1 ≤ k ≤ ⌊ r / 2 ⌋ 1\leq k\leq\lfloor r/2\rfloor 1 ≤ k ≤ ⌊ r /2 ⌋ (11) , we thus have
R g r ( γ , r ) ≤ min 1 ≤ k ≤ ⌊ r / 2 ⌋ 2 k + λ k + λ ( k r − k + λ k + λ ) , R_{\mathrm{gr}}(\gamma,r)\leq\min_{1\leq k\leq\lfloor r/2\rfloor}\frac{2k+\lambda}{k+\lambda}\left(\frac{k}{r-k}+\frac{\lambda}{k+\lambda}\right), R gr ( γ , r ) ≤ 1 ≤ k ≤ ⌊ r /2 ⌋ min k + λ 2 k + λ ( r − k k + k + λ λ ) , where λ ≜ γ 1 − γ \lambda\triangleq\frac{\gamma}{1-\gamma} λ ≜ 1 − γ γ
R g r ( γ , r ) ≤ 1 r max { 8 λ , 2 λ } . R_{\mathrm{gr}}(\gamma,r) \le\frac{1}{\sqrt{r}}\max\left\{8\sqrt{\lambda},\frac{2}{\sqrt{\lambda}}\right\}. R gr ( γ , r ) ≤ r 1 max { 8 λ , λ 2 } . First, we suppose that λ r ≥ 4 \lambda r \ge4 λ r ≥ 4 r ≥ 4 λ r \ge4\lambda r ≥ 4 λ
k = ⌊ λ r ⌋ , N = r − k . k=\left\lfloor\sqrt{\lambda r}\right\rfloor,\qquad N=r-k. k = ⌊ λ r ⌋ , N = r − k . Then
1 2 λ r ≤ k ≤ λ r ≤ r 2 , N = r − k ≥ r 2 , \frac{1}{2}\sqrt{\lambda r}\le k\le\sqrt{\lambda r}\le\frac{r}{2},\qquad N=r-k\ge\frac{r}{2}, 2 1 λ r ≤ k ≤ λ r ≤ 2 r , N = r − k ≥ 2 r , so Eq. (11) gives
R g r ( γ , r ) ≤ 2 ( k N + λ k ) ≤ 2 ( 2 λ r + 2 λ r ) = 8 λ r ≤ 1 r max { 8 λ , 2 λ } . R_{\mathrm{gr}}(\gamma,r)\le2\left(\frac{k}{N}+\frac{\lambda}{k}\right)\le2\left(2\sqrt{\frac{\lambda}{r}}+2\sqrt{\frac{\lambda}{r}}\right)=\frac{8\sqrt{\lambda}}{\sqrt{r}}\le\frac{1}{\sqrt{r}}\max\left\{8\sqrt{\lambda},\frac{2}{\sqrt{\lambda}}\right\}. R gr ( γ , r ) ≤ 2 ( N k + k λ ) ≤ 2 ( 2 r λ + 2 r λ ) = r 8 λ ≤ r 1 max { 8 λ , λ 2 } . If λ r < 4 \lambda r<4 λ r < 4
1 r max { 8 λ , 2 λ } ≥ 2 λ r > 1 ≥ R g r ( γ , r ) . \frac{1}{\sqrt{r}}\max\left\{8\sqrt{\lambda},\frac{2}{\sqrt{\lambda}}\right\}\ge\frac{2}{\sqrt{\lambda r}}>1\ge R_{\mathrm{gr}}(\gamma,r). r 1 max { 8 λ , λ 2 } ≥ λ r 2 > 1 ≥ R gr ( γ , r ) . If r < 4 λ r<4\lambda r < 4 λ
1 r max { 8 λ , 2 λ } ≥ 2 λ r > 1 ≥ R g r ( γ , r ) . \frac{1}{\sqrt{r}}\max\left\{8\sqrt{\lambda},\frac{2}{\sqrt{\lambda}}\right\}\ge\frac{2\sqrt{\lambda}}{\sqrt{r}}>1\ge R_{\mathrm{gr}}(\gamma,r). r 1 max { 8 λ , λ 2 } ≥ r 2 λ > 1 ≥ R gr ( γ , r ) . Thus, in all cases, we obtain
R g r ( γ , r ) ≤ 1 r max { 8 λ , 2 λ } . R_{\mathrm{gr}}(\gamma,r)\le\frac{1}{\sqrt{r}}\max\left\{8\sqrt{\lambda},\frac{2}{\sqrt{\lambda}}\right\}. R gr ( γ , r ) ≤ r 1 max { 8 λ , λ 2 } . Proof of Lemma 3.4
Proof. Set Q ≜ x p + s p Q\triangleq x^p+s^p Q ≜ x p + s p x , s > 0 x,s>0 x , s > 0
∂ x Ψ p ( x , s ) = s p + 1 Q − 1 − 1 / p , ∂ s Ψ p ( x , s ) = x p + 1 Q − 1 − 1 / p . \partial_x\Psi_p(x,s)=s^{p+1}Q^{-1-1/p},\qquad\partial_s\Psi_p(x,s)=x^{p+1}Q^{-1-1/p}. ∂ x Ψ p ( x , s ) = s p + 1 Q − 1 − 1/ p , ∂ s Ψ p ( x , s ) = x p + 1 Q − 1 − 1/ p . Both partial derivatives are nonnegative, so Ψ p \Psi_p Ψ p Ψ p \Psi_p Ψ p
∇ 2 Ψ p ( x , s ) = − ( p + 1 ) x p − 1 s p − 1 Q − 2 − 1 / p ( s 2 − x s − x s x 2 ) . \nabla^2\Psi_p(x,s)=-(p+1)x^{p-1}s^{p-1}Q^{-2-1/p}
\begin{pmatrix}
s^2 & -xs\\
-xs & x^2
\end{pmatrix}. ∇ 2 Ψ p ( x , s ) = − ( p + 1 ) x p − 1 s p − 1 Q − 2 − 1/ p ( s 2 − x s − x s x 2 ) . Its diagonal entries are nonpositive and its determinant is zero; hence the Hessian is negative semidefinite, and Ψ p \Psi_p Ψ p x > 0 x>0 x > 0
∂ s + Ψ p ( x , 0 ) = lim h ↓ 0 Ψ p ( x , h ) − Ψ p ( x , 0 ) h = lim h ↓ 0 x ( x p + h p ) 1 / p = 1. \partial_s^+\Psi_p(x,0)=\lim_{h\downarrow0}\frac{\Psi_p(x,h)-\Psi_p(x,0)}{h}=\lim_{h\downarrow0}\frac{x}{(x^p+h^p)^{1/p}}=1. ∂ s + Ψ p ( x , 0 ) = h ↓ 0 lim h Ψ p ( x , h ) − Ψ p ( x , 0 ) = h ↓ 0 lim ( x p + h p ) 1/ p x = 1. Finally, the inequality ( x p + s p ) 1 / p ≥ max { x , s } (x^p+s^p)^{1/p}\ge\max\{x,s\} ( x p + s p ) 1/ p ≥ max { x , s } Ψ p ( x , s ) ≤ min { x , s } \Psi_p(x,s)\le\min\{x,s\} Ψ p ( x , s ) ≤ min { x , s }
Proof of Lemma 3.5
Proof. Fix A ⊆ C ⊆ U A \subseteq C \subseteq U A ⊆ C ⊆ U
q = ∣ A ∩ G ∣ , s = ∣ A ∩ E ∣ , u = ∣ ( C ∖ A ) ∩ G ∣ , v = ∣ ( C ∖ A ) ∩ E ∣ . q = |A \cap G|,\qquad s = |A \cap E|,\qquad u = |(C \setminus A) \cap G|,\qquad v = |(C \setminus A) \cap E|. q = ∣ A ∩ G ∣ , s = ∣ A ∩ E ∣ , u = ∣ ( C ∖ A ) ∩ G ∣ , v = ∣ ( C ∖ A ) ∩ E ∣. Since q ≥ 1 q \ge1 q ≥ 1 x = a q x = aq x = a q x ≥ a x \ge a x ≥ a B B B Ψ ^ a , p \widehat{\Psi}_{a,p} Ψ a , p
∑ e ∈ C ∖ A ( Ψ ^ a , p ( A + e ) − Ψ ^ a , p ( A ) ) = u ( Ψ p ( x + a , s ) − Ψ p ( x , s ) ) + v ( Ψ p ( x , s + 1 ) − Ψ p ( x , s ) ) . (38) \sum_{e \in C \setminus A} \left(\widehat{\Psi}_{a,p}(A+e)-\widehat{\Psi}_{a,p}(A)\right)
= u\left(\Psi_p(x+a,s)-\Psi_p(x,s)\right)+v\left(\Psi_p(x,s+1)-\Psi_p(x,s)\right). \tag*{(38)} e ∈ C ∖ A ∑ ( Ψ a , p ( A + e ) − Ψ a , p ( A ) ) = u ( Ψ p ( x + a , s ) − Ψ p ( x , s ) ) + v ( Ψ p ( x , s + 1 ) − Ψ p ( x , s ) ) . (38) We first consider the marginal of a good element. If s = 0 s=0 s = 0 Ψ p ( x + a , s ) − Ψ p ( x , s ) \Psi_p(x+a,s)-\Psi_p(x,s) Ψ p ( x + a , s ) − Ψ p ( x , s ) ∂ x Ψ p ( x , s ) \partial_x\Psi_p(x,s) ∂ x Ψ p ( x , s ) s > 0 s>0 s > 0
Ψ p ( x + a , s ) − Ψ p ( x , s ) = a ∫ 0 1 ∂ x Ψ p ( x + a t , s ) d t . \Psi_p(x+a,s)-\Psi_p(x,s)=a\int_0^1\partial_x\Psi_p(x+at,s)\,\mathrm{d}t. Ψ p ( x + a , s ) − Ψ p ( x , s ) = a ∫ 0 1 ∂ x Ψ p ( x + a t , s ) d t . For every t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] x + a t ≤ x ( 1 + t ) x+at\le x(1+t) x + a t ≤ x ( 1 + t )
∂ x Ψ p ( x + a t , s ) ∂ x Ψ p ( x , s ) = ( x p + s p ( x + a t ) p + s p ) 1 + 1 / p ≥ ( 1 + t ) − p − 1 . \frac{\partial_x\Psi_p(x+at,s)}{\partial_x\Psi_p(x,s)}
=\left(\frac{x^p+s^p}{(x+at)^p+s^p}\right)^{1+1/p}
\ge(1+t)^{-p-1}. ∂ x Ψ p ( x , s ) ∂ x Ψ p ( x + a t , s ) = ( ( x + a t ) p + s p x p + s p ) 1 + 1/ p ≥ ( 1 + t ) − p − 1 . Consequently, for any s ≥ 0 s\ge0 s ≥ 0
Ψ p ( x + a , s ) − Ψ p ( x , s ) ≥ a ∂ x Ψ p ( x , s ) ∫ 0 1 ( 1 + t ) − p − 1 d t = c p a ∂ x Ψ p ( x , s ) , \Psi_p(x+a,s)-\Psi_p(x,s)\ge a\partial_x\Psi_p(x,s)\int_0^1(1+t)^{-p-1}\,\mathrm{d}t=c_pa\partial_x\Psi_p(x,s), Ψ p ( x + a , s ) − Ψ p ( x , s ) ≥ a ∂ x Ψ p ( x , s ) ∫ 0 1 ( 1 + t ) − p − 1 d t = c p a ∂ x Ψ p ( x , s ) , where c p ≜ ( 1 − 2 − p ) / p c_p\triangleq(1-2^{-p})/p c p ≜ ( 1 − 2 − p ) / p s ≥ 1 s\ge1 s ≥ 1 s + t ≤ s ( 1 + t ) s+t\le s(1+t) s + t ≤ s ( 1 + t )
∂ s Ψ p ( x , s + t ) ∂ s Ψ p ( x , s ) = ( x p + s p x p + ( s + t ) p ) 1 + 1 / p ≥ ( 1 + t ) − p − 1 . \frac{\partial_s\Psi_p(x,s+t)}{\partial_s\Psi_p(x,s)}
=\left(\frac{x^p+s^p}{x^p+(s+t)^p}\right)^{1+1/p}
\ge(1+t)^{-p-1}. ∂ s Ψ p ( x , s ) ∂ s Ψ p ( x , s + t ) = ( x p + ( s + t ) p x p + s p ) 1 + 1/ p ≥ ( 1 + t ) − p − 1 . Thus, for s ≥ 1 s\ge1 s ≥ 1
Ψ p ( x , s + 1 ) − Ψ p ( x , s ) ≥ c p ∂ s Ψ p ( x , s ) . (39) \Psi_p(x,s+1)-\Psi_p(x,s)\ge c_p\partial_s\Psi_p(x,s). \tag*{(39)} Ψ p ( x , s + 1 ) − Ψ p ( x , s ) ≥ c p ∂ s Ψ p ( x , s ) . (39) When s = 0 s=0 s = 0 Ψ p ( x , 0 ) = 0 \Psi_p(x,0)=0 Ψ p ( x , 0 ) = 0
Ψ p ( x , 1 ) − Ψ p ( x , 0 ) = Ψ p ( x , 1 ) = x ( x p + 1 ) 1 / p ≥ 2 − 1 / p ≥ c p = c p ∂ s + Ψ p ( x , 0 ) , \Psi_p(x,1)-\Psi_p(x,0)=\Psi_p(x,1)=\frac{x}{(x^p+1)^{1/p}}\ge2^{-1/p}\ge c_p=c_p\partial_s^+\Psi_p(x,0), Ψ p ( x , 1 ) − Ψ p ( x , 0 ) = Ψ p ( x , 1 ) = ( x p + 1 ) 1/ p x ≥ 2 − 1/ p ≥ c p = c p ∂ s + Ψ p ( x , 0 ) , where the first inequality comes from x ≥ a ≥ 1 x\ge a\ge1 x ≥ a ≥ 1 p ≥ 1 p\ge1 p ≥ 1 c p ≤ 1 / 2 ≤ 2 − 1 / p c_p\le1/2\le2^{-1/p} c p ≤ 1/2 ≤ 2 − 1/ p (38) -Eq. (39) that
∑ e ∈ C ∖ A ( Ψ ^ a , p ( A + e ) − Ψ ^ a , p ( A ) ) ≥ c p ( a u ∂ x Ψ p ( x , s ) + v ∂ s Ψ p ( x , s ) ) . (40) \sum_{e\in C\setminus A}\left(\widehat{\Psi}_{a,p}(A+e)-\widehat{\Psi}_{a,p}(A)\right)\ge c_p\left(au\partial_x\Psi_p(x,s)+v\partial_s\Psi_p(x,s)\right). \tag*{(40)} e ∈ C ∖ A ∑ ( Ψ a , p ( A + e ) − Ψ a , p ( A ) ) ≥ c p ( a u ∂ x Ψ p ( x , s ) + v ∂ s Ψ p ( x , s ) ) . (40) where ∂ s \partial_s ∂ s s = 0 s=0 s = 0 Ψ p \Psi_p Ψ p s ≥ 1 s\ge1 s ≥ 1
Ψ p ( x + a u , s + v ) − Ψ p ( x , s ) ≤ a u ∂ x Ψ p ( x , s ) + v ∂ s Ψ p ( x , s ) . \Psi_p(x+au,s+v)-\Psi_p(x,s)\le au\partial_x\Psi_p(x,s)+v\partial_s\Psi_p(x,s). Ψ p ( x + a u , s + v ) − Ψ p ( x , s ) ≤ a u ∂ x Ψ p ( x , s ) + v ∂ s Ψ p ( x , s ) . As for s = 0 s=0 s = 0 Ψ p ( x + a u , v ) ≤ v \Psi_p(x+au,v)\le v Ψ p ( x + a u , v ) ≤ v ∂ x Ψ p ( x , 0 ) = 0 \partial_x\Psi_p(x,0)=0 ∂ x Ψ p ( x , 0 ) = 0 ∂ s + Ψ p ( x , 0 ) = 1 \partial_s^+\Psi_p(x,0)=1 ∂ s + Ψ p ( x , 0 ) = 1
Ψ p ( x + a u , v ) − Ψ p ( x , 0 ) = Ψ p ( x + a u , v ) ≤ v = a u ∂ x Ψ p ( x , 0 ) + v ∂ s + Ψ p ( x , 0 ) . \Psi_p(x+au,v)-\Psi_p(x,0)=\Psi_p(x+au,v)\le v=au\partial_x\Psi_p(x,0)+v\partial_s^+\Psi_p(x,0). Ψ p ( x + a u , v ) − Ψ p ( x , 0 ) = Ψ p ( x + a u , v ) ≤ v = a u ∂ x Ψ p ( x , 0 ) + v ∂ s + Ψ p ( x , 0 ) . Combining this inequality with Eq. (40) gives Eq. (16) .
Proof of Lemma 3.6
Proof. Since H p , τ , k ( 0 , 0 ) = 0 H_{p,\tau,k}(0,0)=0 H p , τ , k ( 0 , 0 ) = 0 A ⊆ C ⊆ U A \subseteq C \subseteq U A ⊆ C ⊆ U
q = ∣ A ∩ G ∣ , s = ∣ A ∩ E ∣ , u = ∣ ( C ∖ A ) ∩ G ∣ , v = ∣ ( C ∖ A ) ∩ E ∣ . q = |A \cap G|,\qquad s = |A \cap E|,\qquad u = |(C \setminus A) \cap G|,\qquad v = |(C \setminus A) \cap E|. q = ∣ A ∩ G ∣ , s = ∣ A ∩ E ∣ , u = ∣ ( C ∖ A ) ∩ G ∣ , v = ∣ ( C ∖ A ) ∩ E ∣. Elements of B B B H ^ p , τ , k \widehat{H}_{p,\tau,k} H p , τ , k H ^ p , τ , k \widehat{H}_{p,\tau,k} H p , τ , k A A A
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) = u ( H p , τ , k ( q + 1 , s ) − H p , τ , k ( q , s ) ) + v ( H p , τ , k ( q , s + 1 ) − H p , τ , k ( q , s ) ) . \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)
=u\bigl(H_{p,\tau,k}(q+1,s)-H_{p,\tau,k}(q,s)\bigr)
+v\bigl(H_{p,\tau,k}(q,s+1)-H_{p,\tau,k}(q,s)\bigr). e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) = u ( H p , τ , k ( q + 1 , s ) − H p , τ , k ( q , s ) ) + v ( H p , τ , k ( q , s + 1 ) − H p , τ , k ( q , s ) ) . and the joint gain is H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) H_{p,\tau,k}(q+u,s+v)-H_{p,\tau,k}(q,s) H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s )
We verify the weak submodularity in three cases. First, we suppose that q ≥ 1 q \ge1 q ≥ 1 (18) . Lemma 3.5 and the inequality γ ≤ c p \gamma\le c_p γ ≤ c p
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) ≥ c p ( H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) ) ≥ γ ( H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) ) . \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)
\ge c_p\bigl(H_{p,\tau,k}(q+u,s+v)-H_{p,\tau,k}(q,s)\bigr)
\ge\gamma\bigl(H_{p,\tau,k}(q+u,s+v)-H_{p,\tau,k}(q,s)\bigr). e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) ≥ c p ( H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) ) ≥ γ ( H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) ) . Second, suppose that q = u = 0 q=u=0 q = u = 0 s ≥ k s\ge k s ≥ k
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) = 0 = H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) . \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)
=0=H_{p,\tau,k}(q+u,s+v)-H_{p,\tau,k}(q,s). e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) = 0 = H p , τ , k ( q + u , s + v ) − H p , τ , k ( q , s ) . If s < k s<k s < k
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) = v ( H p , τ , k ( q , s + 1 ) − H p , τ , k ( q , s ) ) = v , \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)
=v\bigl(H_{p,\tau,k}(q,s+1)-H_{p,\tau,k}(q,s)\bigr)=v, e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) = v ( H p , τ , k ( q , s + 1 ) − H p , τ , k ( q , s ) ) = v , H p , τ , k ( 0 , s + v ) − H p , τ , k ( 0 , s ) = min { s + v , k } − s ≤ v . H_{p,\tau,k}(0,s+v)-H_{p,\tau,k}(0,s)=\min\{s+v,k\}-s\le v. H p , τ , k ( 0 , s + v ) − H p , τ , k ( 0 , s ) = min { s + v , k } − s ≤ v . Since γ ≤ 1 \gamma\le1 γ ≤ 1
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) ≥ γ ( H p , τ , k ( 0 , s + v ) − H p , τ , k ( 0 , s ) ) . \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)
\ge\gamma\bigl(H_{p,\tau,k}(0,s+v)-H_{p,\tau,k}(0,s)\bigr). e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) ≥ γ ( H p , τ , k ( 0 , s + v ) − H p , τ , k ( 0 , s ) ) . It remains to consider q = 0 q=0 q = 0 u ≥ 1 u\ge1 u ≥ 1
Δ g ( s ) = H p , τ , k ( 1 , s ) − H p , τ , k ( 0 , s ) , Δ e ( s ) = H p , τ , k ( 0 , s + 1 ) − H p , τ , k ( 0 , s ) . \Delta_g(s)=H_{p,\tau,k}(1,s)-H_{p,\tau,k}(0,s),\qquad
\Delta_e(s)=H_{p,\tau,k}(0,s+1)-H_{p,\tau,k}(0,s). Δ g ( s ) = H p , τ , k ( 1 , s ) − H p , τ , k ( 0 , s ) , Δ e ( s ) = H p , τ , k ( 0 , s + 1 ) − H p , τ , k ( 0 , s ) . Then, we have
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) = u Δ g ( s ) + v Δ e ( s ) . \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)=u\Delta_g(s)+v\Delta_e(s). e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) = u Δ g ( s ) + v Δ e ( s ) . Suppose first that s < k s<k s < k Δ e ( s ) = 1 \Delta_e(s)=1 Δ e ( s ) = 1 s / a = ( s / k ) τ ≤ τ s/a=(s/k)^\tau\le\tau s / a = ( s / k ) τ ≤ τ s > 0 s>0 s > 0
γ ≜ τ ( 1 + τ ) ( 1 + τ p ) 1 / p , \gamma\triangleq\frac{\tau}{(1+\tau)(1+\tau^p)^{1/p}}, γ ≜ ( 1 + τ ) ( 1 + τ p ) 1/ p τ , we can show that
γ − 1 Ψ p ( a , s ) = γ − 1 s ( 1 + ( s / a ) p ) 1 / p ≥ γ − 1 s ( 1 + τ p ) 1 / p = 1 + τ τ s ≥ 2 s . \gamma^{-1}\Psi_p(a,s)
=\frac{\gamma^{-1}s}{(1+(s/a)^p)^{1/p}}
\ge\frac{\gamma^{-1}s}{(1+\tau^p)^{1/p}}
=\frac{1+\tau}{\tau}s\ge2s. γ − 1 Ψ p ( a , s ) = ( 1 + ( s / a ) p ) 1/ p γ − 1 s ≥ ( 1 + τ p ) 1/ p γ − 1 s = τ 1 + τ s ≥ 2 s . Therefore, we can show that Δ g ( s ) = γ − 1 Ψ p ( a , s ) − s ≥ s \Delta_g(s)=\gamma^{-1}\Psi_p(a,s)-s\ge s Δ g ( s ) = γ − 1 Ψ p ( a , s ) − s ≥ s s = 0 s=0 s = 0 u ≥ 1 u\ge1 u ≥ 1
∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) = u Δ g ( s ) + v Δ e ( s ) ≥ u s + v ≥ s + v . \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)
=u\Delta_g(s)+v\Delta_e(s)\ge us+v\ge s+v. e ∈ C ∖ A ∑ H p , τ , k ( e ∣ A ) = u Δ g ( s ) + v Δ e ( s ) ≥ u s + v ≥ s + v . On the other hand,
γ ( H p , τ , k ( u , s + v ) − H p , τ , k ( 0 , s ) ) = Ψ p ( a u , s + v ) − γ s ≤ Ψ p ( a u , s + v ) ≤ s + v . \gamma\left(H_{p,\tau,k}(u,s+v)-H_{p,\tau,k}(0,s)\right)=\Psi_p(au,s+v)-\gamma s\le\Psi_p(au,s+v)\le s+v. γ ( H p , τ , k ( u , s + v ) − H p , τ , k ( 0 , s ) ) = Ψ p ( a u , s + v ) − γ s ≤ Ψ p ( a u , s + v ) ≤ s + v . Combining the last two displays proves the γ \gamma γ s < k s<k s < k
Finally, we suppose that s ≥ k s\ge k s ≥ k Δ e ( s ) = 0 \Delta_e(s)=0 Δ e ( s ) = 0 Ψ p ( a , s ) \Psi_p(a,s) Ψ p ( a , s ) s s s Δ g ( s ) = H p , τ , k ( 1 , s ) − k \Delta_g(s)=H_{p,\tau,k}(1,s)-k Δ g ( s ) = H p , τ , k ( 1 , s ) − k k = a τ k=a\tau k = a τ (17) give
Δ g ( k ) = γ − 1 Ψ p ( a , a τ ) − a τ = a τ γ ( 1 + τ p ) 1 / p − a τ = a ( 1 + τ ) − a τ = a . \Delta_g(k)=\gamma^{-1}\Psi_p(a,a\tau)-a\tau=\frac{a\tau}{\gamma(1+\tau^p)^{1/p}}-a\tau=a(1+\tau)-a\tau=a. Δ g ( k ) = γ − 1 Ψ p ( a , a τ ) − a τ = γ ( 1 + τ p ) 1/ p a τ − a τ = a ( 1 + τ ) − a τ = a . Consequently, ∑ e ∈ C ∖ A H ^ p , τ , k ( e ∣ A ) = u Δ g ( s ) ≥ u Δ g ( k ) = u a \sum_{e\in C\setminus A}\widehat{H}_{p,\tau,k}(e\mid A)=u\Delta_g(s)\ge u\Delta_g(k)=ua ∑ e ∈ C ∖ A H p , τ , k ( e ∣ A ) = u Δ g ( s ) ≥ u Δ g ( k ) = u a
The joint gain satisfies
γ ( H p , τ , k ( u , s + v ) − H p , τ , k ( 0 , s ) ) = Ψ p ( a u , s + v ) − γ k ≤ Ψ p ( a u , s + v ) ≤ a u . \gamma\left(H_{p,\tau,k}(u,s+v)-H_{p,\tau,k}(0,s)\right)=\Psi_p(au,s+v)-\gamma k\le\Psi_p(au,s+v)\le au. γ ( H p , τ , k ( u , s + v ) − H p , τ , k ( 0 , s ) ) = Ψ p ( a u , s + v ) − γ k ≤ Ψ p ( a u , s + v ) ≤ a u . Thus the weak submodularity also holds when s ≥ k s\ge k s ≥ k
Proof of Proposition 3.7
Proof. For the power-mean upper bound, we assume N = r − k ≥ k N=r-k\ge k N = r − k ≥ k 1 ≤ k ≤ ⌊ r / 2 ⌋ 1\le k\le\lfloor r/2\rfloor 1 ≤ k ≤ ⌊ r /2 ⌋ (22) , we then can get the upper bound in Eq. (23) .
Proof of Theorem 3.8
Proof. In this section, we prove the uniform upper bound presented in Eq. (24) . We divide the parameter range into three parts. First, we suppose that 0 < γ ≤ 1 / ( 2 2 ) 0<\gamma\le1/(2\sqrt{2}) 0 < γ ≤ 1/ ( 2 2 ) p = 2 p=2 p = 2 (17) , namely γ ≜ τ ( 1 + τ ) 1 + τ 2 \gamma\triangleq\frac{\tau}{(1+\tau)\sqrt{1+\tau^2}} γ ≜ ( 1 + τ ) 1 + τ 2 τ τ 2 2 ≤ γ ≤ τ \frac{\tau}{2\sqrt{2}}\le\gamma\le\tau 2 2 τ ≤ γ ≤ τ τ r < 4 \tau r<4 τ r < 4 k = 1 k=1 k = 1 (23) such that
R g r ( γ , r ) ≤ 2 γ [ 1 ( r − 1 ) 2 + τ 2 ] 1 / 2 ≤ 2 γ [ 4 r 2 + 16 r 2 ] 1 / 2 = 4 5 γ r < 9 γ r , R_{\mathrm{gr}}(\gamma,r)\le2\gamma\left[\frac{1}{(r-1)^2}+\tau^2\right]^{1/2}\le2\gamma\left[\frac{4}{r^2}+\frac{16}{r^2}\right]^{1/2}=4\sqrt{5}\frac{\gamma}{r}<\frac{9\gamma}{r}, R gr ( γ , r ) ≤ 2 γ [ ( r − 1 ) 2 1 + τ 2 ] 1/2 ≤ 2 γ [ r 2 4 + r 2 16 ] 1/2 = 4 5 r γ < r 9 γ , where the second inequality comes from 1 / ( r − 1 ) ≤ 2 / r ( r ≥ 2 ) 1/(r-1)\le2/r(r\ge2) 1/ ( r − 1 ) ≤ 2/ r ( r ≥ 2 ) τ < 4 / r \tau<4/r τ < 4/ r R g r ( γ , r ) < 9 γ / r ≤ 9 Φ ( γ , r ) R_{\mathrm{gr}}(\gamma,r)<9\gamma/r\le9\Phi(\gamma,r) R gr ( γ , r ) < 9 γ / r ≤ 9Φ ( γ , r )
Φ ( γ , r ) ≜ max { γ r , γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) } . \Phi(\gamma,r)\triangleq\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\right\}. Φ ( γ , r ) ≜ max { r γ , B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 } . If τ r ≥ 4 \tau r\ge4 τ r ≥ 4 k = ⌊ τ r ⌋ k=\lfloor\sqrt{\tau r}\rfloor k = ⌊ τ r ⌋ τ ≤ 1 \tau\le1 τ ≤ 1 τ r ≥ 4 \tau r\ge4 τ r ≥ 4 r ≥ 4 r\ge4 r ≥ 4
1 2 τ r ≤ k ≤ τ r ≤ r ≤ r 2 , r − k ≥ r 2 . \frac{1}{2}\sqrt{\tau r}\le k\le\sqrt{\tau r}\le\sqrt r\le\frac{r}{2},\qquad r-k\ge\frac r2. 2 1 τ r ≤ k ≤ τ r ≤ r ≤ 2 r , r − k ≥ 2 r . Substitution into Eq. (23) gives
R g r ( γ , r ) ≤ 2 γ [ ( k r − k ) 2 + ( τ k ) 2 ] 1 / 2 ≤ 2 γ [ 4 τ r + 4 τ r ] 1 / 2 = 4 2 γ τ r ≤ 2 13 / 4 γ 3 / 2 r , ( 42 ) R_{\mathrm{gr}}(\gamma,r)\le2\gamma\left[\left(\frac{k}{r-k}\right)^2+\left(\frac{\tau}{k}\right)^2\right]^{1/2}\le2\gamma\left[4\frac{\tau}{r}+4\frac{\tau}{r}\right]^{1/2}=4\sqrt{2}\gamma\sqrt{\frac{\tau}{r}}\le2^{13/4}\frac{\gamma^{3/2}}{\sqrt r},\qquad(42) R gr ( γ , r ) ≤ 2 γ [ ( r − k k ) 2 + ( k τ ) 2 ] 1/2 ≤ 2 γ [ 4 r τ + 4 r τ ] 1/2 = 4 2 γ r τ ≤ 2 13/4 r γ 3/2 , ( 42 ) where the final inequality comes from τ ≤ 2 2 γ \tau\le2\sqrt{2\gamma} τ ≤ 2 2 γ y ≜ γ r y\triangleq\sqrt{\gamma r} y ≜ γ r B γ ≜ 2 − γ + γ 2 ≤ 2 B_\gamma\triangleq2-\gamma+\gamma^2\le2 B γ ≜ 2 − γ + γ 2 ≤ 2 γ ( 1 − γ ) ( r − 1 ) ≤ y \sqrt{\gamma(1-\gamma)(r-1)}\le y γ ( 1 − γ ) ( r − 1 ) ≤ y
Φ ( γ , r ) ≜ max { γ r , γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) } ≥ γ 2 max { y − 2 , ( 2 + y ) − 1 } . \Phi(\gamma,r)\triangleq\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\right\}\ge\gamma^2\max\{y^{-2},(2+y)^{-1}\}. Φ ( γ , r ) ≜ max { r γ , B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 } ≥ γ 2 max { y − 2 , ( 2 + y ) − 1 } . If y ≤ 2 y \le2 y ≤ 2 γ 2 / y ≤ 2 γ 2 / y 2 \gamma^2/y \le2\gamma^2/y^2 γ 2 / y ≤ 2 γ 2 / y 2 y ≥ 2 y \ge2 y ≥ 2 γ 2 / y ≤ 2 γ 2 / ( 2 + y ) \gamma^2/y \le2\gamma^2/(2+y) γ 2 / y ≤ 2 γ 2 / ( 2 + y ) γ 3 / 2 / r = γ 2 / y ≤ 2 Φ ( γ , r ) \gamma^{3/2}/\sqrt{r}=\gamma^2/y \le2\Phi(\gamma,r) γ 3/2 / r = γ 2 / y ≤ 2Φ ( γ , r )
Together with Eq. (42), this gives R g r ( γ , r ) ≤ 2 17 / 4 Φ ( γ , r ) < 20 Φ ( γ , r ) R_{\mathrm{gr}}(\gamma,r) \le2^{17/4}\Phi(\gamma,r)<20\Phi(\gamma,r) R gr ( γ , r ) ≤ 2 17/4 Φ ( γ , r ) < 20Φ ( γ , r )
Next, we suppose
1 2 2 ≤ γ ≤ 1 2 , λ ≜ γ 1 − γ , x ≜ λ r . \frac{1}{2\sqrt{2}}\le\gamma\le\frac{1}{2},\qquad\lambda\triangleq\frac{\gamma}{1-\gamma},\qquad x\triangleq\sqrt{\lambda r}. 2 2 1 ≤ γ ≤ 2 1 , λ ≜ 1 − γ γ , x ≜ λ r . If x < 3 x<3 x < 3
B γ + γ ( 1 − γ ) ( r − 1 ) = B γ + ( 1 − γ ) ⋅ γ 1 − γ ( r − 1 ) = B γ + ( 1 − γ ) x < B γ + 3 ( 1 − γ ) ≤ 40 γ 2 . B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}=B_\gamma+(1-\gamma)\cdot\sqrt{\frac{\gamma}{1-\gamma}(r-1)}=B_\gamma+(1-\gamma)x<B_\gamma+3(1-\gamma)\le40\gamma^2. B γ + γ ( 1 − γ ) ( r − 1 ) = B γ + ( 1 − γ ) ⋅ 1 − γ γ ( r − 1 ) = B γ + ( 1 − γ ) x < B γ + 3 ( 1 − γ ) ≤ 40 γ 2 . where the final inequality follows from that B γ + 3 ( 1 − γ ) = 5 − 4 γ + γ 2 B_\gamma+3(1-\gamma)=5-4\gamma+\gamma^2 B γ + 3 ( 1 − γ ) = 5 − 4 γ + γ 2 1 2 2 ≤ γ ≤ 1 2 \frac{1}{2\sqrt{2}}\le\gamma\le\frac{1}{2} 2 2 1 ≤ γ ≤ 2 1 40 γ 2 40\gamma^2 40 γ 2 γ = 1 / ( 2 2 ) \gamma=1/(2\sqrt{2}) γ = 1/ ( 2 2 ) B γ + 3 ( 1 − γ ) = 41 / 8 − 2 ≤ 5 = 40 γ 2 B_\gamma+3(1-\gamma)=41/8-\sqrt{2}\le5=40\gamma^2 B γ + 3 ( 1 − γ ) = 41/8 − 2 ≤ 5 = 40 γ 2
As a result, according to Eq. (14) , we have
R g r ( γ , r ) ≤ 1 2 = 20 γ 2 40 γ 2 ≤ 20 γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) ≤ 20 Φ ( γ , r ) . R_{\mathrm{gr}}(\gamma,r)\le\frac{1}{2}=20\frac{\gamma^2}{40\gamma^2}\le20\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\le20\Phi(\gamma,r). R gr ( γ , r ) ≤ 2 1 = 20 40 γ 2 γ 2 ≤ 20 B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 ≤ 20Φ ( γ , r ) . Now, we assume that x ≥ 3 x\ge3 x ≥ 3 k = ⌊ x ⌋ k=\lfloor x\rfloor k = ⌊ x ⌋ λ ≜ γ 1 − γ ≤ 1 \lambda\triangleq\frac{\gamma}{1-\gamma}\le1 λ ≜ 1 − γ γ ≤ 1 x ≥ 3 x\ge3 x ≥ 3 1 ≤ k ≤ r / 2 1\le k\le r/2 1 ≤ k ≤ r /2
k r − k ≤ x r − x = x x 2 / λ − x = λ x − λ , λ k + λ ≤ λ x − 1 + λ , \frac{k}{r-k}\le\frac{x}{r-x}=\frac{x}{x^2/\lambda-x}=\frac{\lambda}{x-\lambda},\qquad\frac{\lambda}{k+\lambda}\le\frac{\lambda}{x-1+\lambda}, r − k k ≤ r − x x = x 2 / λ − x x = x − λ λ , k + λ λ ≤ x − 1 + λ λ , where the first term comes from x ≥ k x\ge k x ≥ k r = x 2 / λ r=x^2/\lambda r = x 2 / λ (12) consequently gives
R g r ( γ , r ) ≤ min { 1 2 , 2 λ ( 1 x − λ + 1 x − 1 + λ ) } . (41) R_{\mathrm{gr}}(\gamma,r)\le\min\left\{\frac{1}{2},2\lambda\left(\frac{1}{x-\lambda}+\frac{1}{x-1+\lambda}\right)\right\}. \tag*{(41)} R gr ( γ , r ) ≤ min { 2 1 , 2 λ ( x − λ 1 + x − 1 + λ 1 ) } . (41) Similarly, in this setting, if B γ + ( 1 − γ ) x ≤ 40 γ 2 B_\gamma+(1-\gamma)x\le40\gamma^2 B γ + ( 1 − γ ) x ≤ 40 γ 2
B γ + γ ( 1 − γ ) ( r − 1 ) = B γ + ( 1 − γ ) ⋅ γ 1 − γ ( r − 1 ) = B γ + ( 1 − γ ) x ≤ 40 γ 2 , B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}=B_\gamma+(1-\gamma)\cdot\sqrt{\frac{\gamma}{1-\gamma}(r-1)}=B_\gamma+(1-\gamma)x\le40\gamma^2, B γ + γ ( 1 − γ ) ( r − 1 ) = B γ + ( 1 − γ ) ⋅ 1 − γ γ ( r − 1 ) = B γ + ( 1 − γ ) x ≤ 40 γ 2 , so R g r ( γ , r ) ≤ 1 2 = 20 γ 2 40 γ 2 ≤ 20 γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) ≤ 20 Φ ( γ , r ) R_{\mathrm{gr}}(\gamma,r)\le\frac{1}{2}=20\frac{\gamma^2}{40\gamma^2}\le20\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\le20\Phi(\gamma,r) R gr ( γ , r ) ≤ 2 1 = 20 40 γ 2 γ 2 ≤ 20 B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 ≤ 20Φ ( γ , r )
Instead, if B γ + ( 1 − γ ) x > 40 γ 2 B_\gamma+(1-\gamma)x>40\gamma^2 B γ + ( 1 − γ ) x > 40 γ 2 h ( x ) ≜ ( B γ + ( 1 − γ ) x ) ( 1 x − λ + 1 x − 1 + λ ) h(x)\triangleq(B_\gamma+(1-\gamma)x)\left(\frac{1}{x-\lambda}+\frac{1}{x-1+\lambda}\right) h ( x ) ≜ ( B γ + ( 1 − γ ) x ) ( x − λ 1 + x − 1 + λ 1 ) (41) , we also can have
R g r ( γ , r ) ≤ 2 λ ( 1 x − λ + 1 x − 1 + λ ) ≤ 2 λ B γ + ( 1 − γ ) x ⋅ h ( x ) . R_{\mathrm{gr}}(\gamma,r)\le2\lambda\left(\frac{1}{x-\lambda}+\frac{1}{x-1+\lambda}\right)\le\frac{2\lambda}{B_\gamma+(1-\gamma)x}\cdot h(x). R gr ( γ , r ) ≤ 2 λ ( x − λ 1 + x − 1 + λ 1 ) ≤ B γ + ( 1 − γ ) x 2 λ ⋅ h ( x ) . Moreover, direct differentiation of h ( x ) h(x) h ( x )
h ′ ( x ) = − ( B γ + ( 1 − γ ) λ ( x − λ ) 2 + B γ + ( 1 − γ ) ( 1 − λ ) ( x − 1 + λ ) 2 ) < 0. h'(x)=-\left(\frac{B_\gamma+(1-\gamma)\lambda}{(x-\lambda)^2}+\frac{B_\gamma+(1-\gamma)(1-\lambda)}{(x-1+\lambda)^2}\right)<0. h ′ ( x ) = − ( ( x − λ ) 2 B γ + ( 1 − γ ) λ + ( x − 1 + λ ) 2 B γ + ( 1 − γ ) ( 1 − λ ) ) < 0. Hence, the function h ( x ) h(x) h ( x ) B γ + ( 1 − γ ) x > 40 γ 2 B_\gamma+(1-\gamma)x>40\gamma^2 B γ + ( 1 − γ ) x > 40 γ 2 h ( x ) ≤ h ( 40 γ 2 − B γ 1 − γ ) h(x)\le h\left(\frac{40\gamma^2-B_\gamma}{1-\gamma}\right) h ( x ) ≤ h ( 1 − γ 40 γ 2 − B γ ) λ = γ / ( 1 − γ ) \lambda=\gamma/(1-\gamma) λ = γ / ( 1 − γ )
h ( 40 γ 2 − B γ 1 − γ ) = 40 γ 2 ( 1 − γ ) ( 1 39 γ 2 − 2 + 1 39 γ 2 + 3 γ − 3 ) . (42) h\left(\frac{40\gamma^2-B_\gamma}{1-\gamma}\right)=40\gamma^2(1-\gamma)\left(\frac{1}{39\gamma^2-2}+\frac{1}{39\gamma^2+3\gamma-3}\right). \tag*{(42)} h ( 1 − γ 40 γ 2 − B γ ) = 40 γ 2 ( 1 − γ ) ( 39 γ 2 − 2 1 + 39 γ 2 + 3 γ − 3 1 ) . (42) With the help of Eq. (42) , we next prove
1 39 γ 2 − 2 + 1 39 γ 2 + 3 γ − 3 ≤ 1 4 γ . \frac{1}{39\gamma^2-2}+\frac{1}{39\gamma^2+3\gamma-3}\leq\frac{1}{4\gamma}. 39 γ 2 − 2 1 + 39 γ 2 + 3 γ − 3 1 ≤ 4 γ 1 . More specifically, we consider the following polynomial function P ( γ ) P(\gamma) P ( γ )
P ( γ ) ≜ ( 39 γ 2 − 2 ) ( 39 γ 2 + 3 γ − 3 ) − 4 γ ( 78 γ 2 + 3 γ − 5 ) = 1521 γ 4 − 195 γ 3 − 207 γ 2 + 14 γ + 6. P(\gamma)\triangleq(39\gamma^2-2)(39\gamma^2+3\gamma-3)-4\gamma(78\gamma^2+3\gamma-5)=1521\gamma^4-195\gamma^3-207\gamma^2+14\gamma+6. P ( γ ) ≜ ( 39 γ 2 − 2 ) ( 39 γ 2 + 3 γ − 3 ) − 4 γ ( 78 γ 2 + 3 γ − 5 ) = 1521 γ 4 − 195 γ 3 − 207 γ 2 + 14 γ + 6. Then, we also can show that, when 1 2 2 ≤ γ ≤ 1 2 \frac{1}{2\sqrt{2}}\leq\gamma\leq\frac{1}{2} 2 2 1 ≤ γ ≤ 2 1
P ′ ′ ′ ( γ ) = 36504 γ − 1170 > 0 , P ′ ′ ( 1 2 2 ) = 3735 − 585 2 2 > 0 , P'''(\gamma)=36504\gamma-1170>0,\qquad P''\left(\frac{1}{2\sqrt{2}}\right)=\frac{3735-585\sqrt{2}}{2}>0, P ′′′ ( γ ) = 36504 γ − 1170 > 0 , P ′′ ( 2 2 1 ) = 2 3735 − 585 2 > 0 , and
P ′ ( 1 2 2 ) = 693 2 − 473 8 > 0. P'\left(\frac{1}{2\sqrt{2}}\right)=\frac{693\sqrt{2}-473}{8}>0. P ′ ( 2 2 1 ) = 8 693 2 − 473 > 0. Thus P P P 1 2 2 ≤ γ ≤ 1 2 \frac{1}{2\sqrt{2}}\leq\gamma\leq\frac{1}{2} 2 2 1 ≤ γ ≤ 2 1 P ( 1 2 2 ) = ( 249 − 166 2 ) / 64 > 0 P\left(\frac{1}{2\sqrt{2}}\right)=(249-166\sqrt{2})/64>0 P ( 2 2 1 ) = ( 249 − 166 2 ) /64 > 0
1 39 γ 2 − 2 + 1 39 γ 2 + 3 γ − 3 ≤ 1 4 γ \frac{1}{39\gamma^2-2}+\frac{1}{39\gamma^2+3\gamma-3}\leq\frac{1}{4\gamma} 39 γ 2 − 2 1 + 39 γ 2 + 3 γ − 3 1 ≤ 4 γ 1 such that
R g r ( γ , r ) ≤ 2 λ ( 1 x − λ + 1 x − 1 + λ ) ≤ 2 λ B γ + ( 1 − γ ) x ⋅ h ( x ) ≤ 2 λ B γ + ( 1 − γ ) x ⋅ h ( 40 γ 2 − B γ 1 − γ ) R_{\mathrm{gr}}(\gamma,r)\leq2\lambda\left(\frac{1}{x-\lambda}+\frac{1}{x-1+\lambda}\right)\leq\frac{2\lambda}{B_\gamma+(1-\gamma)x}\cdot h(x)\leq\frac{2\lambda}{B_\gamma+(1-\gamma)x}\cdot h\left(\frac{40\gamma^2-B_\gamma}{1-\gamma}\right) R gr ( γ , r ) ≤ 2 λ ( x − λ 1 + x − 1 + λ 1 ) ≤ B γ + ( 1 − γ ) x 2 λ ⋅ h ( x ) ≤ B γ + ( 1 − γ ) x 2 λ ⋅ h ( 1 − γ 40 γ 2 − B γ ) ≤ 20 γ 2 B γ + ( 1 − γ ) x ≤ 20 Φ ( γ , r ) . \leq20\frac{\gamma^2}{B_\gamma+(1-\gamma)x}\leq20\Phi(\gamma,r). ≤ 20 B γ + ( 1 − γ ) x γ 2 ≤ 20Φ ( γ , r ) . Finally, we consider that 1 / 2 ≤ γ < 1 1/2\leq\gamma<1 1/2 ≤ γ < 1 λ = γ / ( 1 − γ ) ≥ 1 \lambda=\gamma/(1-\gamma)\geq1 λ = γ / ( 1 − γ ) ≥ 1 (13) becomes
R g r ( γ , r ) ≤ 1 r max { 8 γ 1 − γ , 2 1 − γ γ } ≤ 8 γ ( 1 − γ ) r = 8 γ γ ( 1 − γ ) r . (43) R_{\mathrm{gr}}(\gamma,r)\leq\frac{1}{\sqrt{r}}\max\left\{8\sqrt{\frac{\gamma}{1-\gamma}},2\sqrt{\frac{1-\gamma}{\gamma}}\right\}\leq8\sqrt{\frac{\gamma}{(1-\gamma)r}}=\frac{8\gamma}{\sqrt{\gamma(1-\gamma)r}}. \tag*{(43)} R gr ( γ , r ) ≤ r 1 max { 8 1 − γ γ , 2 γ 1 − γ } ≤ 8 ( 1 − γ ) r γ = γ ( 1 − γ ) r 8 γ . (43) If γ ( 1 − γ ) r ≥ 16 γ \sqrt{\gamma(1-\gamma)r}\geq16\gamma γ ( 1 − γ ) r ≥ 16 γ γ ( 1 − γ ) r > 8 \sqrt{\gamma(1-\gamma)r}>8 γ ( 1 − γ ) r > 8 B γ ≤ 2 < γ ( 1 − γ ) r / 4 B_\gamma\leq2<\sqrt{\gamma(1-\gamma)r}/4 B γ ≤ 2 < γ ( 1 − γ ) r /4 γ ( 1 − γ ) ( r − 1 ) ≤ ( 1 − γ ) r \sqrt{\gamma(1-\gamma)(r-1)}\leq\sqrt{(1-\gamma)r} γ ( 1 − γ ) ( r − 1 ) ≤ ( 1 − γ ) r (43) , we can show that
R g r ( γ , r ) ≤ 8 γ γ ( 1 − γ ) r = 16 ⋅ ( γ / 2 ) γ ( 1 − γ ) r ≤ 16 γ 2 γ ( 1 − γ ) r = 20 γ 2 γ ( 1 − γ ) r / 4 + γ ( 1 − γ ) r R_{\mathrm{gr}}(\gamma,r)\leq\frac{8\gamma}{\sqrt{\gamma(1-\gamma)r}}=\frac{16\cdot(\gamma/2)}{\sqrt{\gamma(1-\gamma)r}}\leq\frac{16\gamma^2}{\sqrt{\gamma(1-\gamma)r}}=\frac{20\gamma^2}{\sqrt{\gamma(1-\gamma)r}/4+\sqrt{\gamma(1-\gamma)r}} R gr ( γ , r ) ≤ γ ( 1 − γ ) r 8 γ = γ ( 1 − γ ) r 16 ⋅ ( γ /2 ) ≤ γ ( 1 − γ ) r 16 γ 2 = γ ( 1 − γ ) r /4 + γ ( 1 − γ ) r 20 γ 2 ≤ 20 γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) ≤ 20 Φ ( γ , r ) . \leq20\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\leq20\Phi(\gamma,r). ≤ 20 B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 ≤ 20Φ ( γ , r ) . When γ ( 1 − γ ) r ≤ 16 γ \sqrt{\gamma(1-\gamma)r}\leq16\gamma γ ( 1 − γ ) r ≤ 16 γ
B γ + γ ( 1 − γ ) ( r − 1 ) ≤ 2 + 16 γ ≤ 40 γ 2 , B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\leq2+16\gamma\leq40\gamma^2, B γ + γ ( 1 − γ ) ( r − 1 ) ≤ 2 + 16 γ ≤ 40 γ 2 , where the last inequality comes from that 40 γ 2 − 16 γ − 2 ≥ 0 40\gamma^2-16\gamma-2\geq0 40 γ 2 − 16 γ − 2 ≥ 0 γ ≥ 1 / 2 \gamma\geq1/2 γ ≥ 1/2
R g r ( γ , r ) ≤ 1 2 ≤ 20 γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) ≤ 20 Φ ( γ , r ) . R_{\mathrm{gr}}(\gamma,r)\leq\frac{1}{2}\leq20\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}\leq20\Phi(\gamma,r). R gr ( γ , r ) ≤ 2 1 ≤ 20 B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 ≤ 20Φ ( γ , r ) . Finally, we have R g r ( γ , r ) ≤ 20 Φ ( γ , r ) R_{\mathrm{gr}}(\gamma,r)\leq20\Phi(\gamma,r) R gr ( γ , r ) ≤ 20Φ ( γ , r ) 0 < γ < 1 0<\gamma<1 0 < γ < 1 γ = 1 \gamma=1 γ = 1 R g r ( 1 , r ) = 1 / 2 R_{\mathrm{gr}}(1,r)=1/2 R gr ( 1 , r ) = 1/2 (24) .
Proofs for the lower bounds
Proof of Lemma 4.1
Proof. Since S t − 1 ⊆ S t S_{t-1} \subseteq S_t S t − 1 ⊆ S t f f f d t = f ( S t ) − f ( S t − 1 ) ≥ 0 d_t = f(S_t) - f(S_{t-1}) \ge0 d t = f ( S t ) − f ( S t − 1 ) ≥ 0 d i = F i − F i − 1 d_i = F_i - F_{i-1} d i = F i − F i − 1
W t = ∑ i = 1 t i ( F i − F i − 1 ) = ∑ i = 1 t i F i − ∑ i = 1 t i F i − 1 = ∑ i = 1 t i F i − ∑ j = 0 t − 1 ( j + 1 ) F j = t F t − ∑ j = 0 t − 1 F j = t F t − K t . W_t = \sum_{i=1}^{t} i(F_i-F_{i-1}) = \sum_{i=1}^{t} iF_i - \sum_{i=1}^{t} iF_{i-1} = \sum_{i=1}^{t} iF_i - \sum_{j=0}^{t-1}(j+1)F_j = tF_t - \sum_{j=0}^{t-1}F_j = tF_t-K_t. W t = i = 1 ∑ t i ( F i − F i − 1 ) = i = 1 ∑ t i F i − i = 1 ∑ t i F i − 1 = i = 1 ∑ t i F i − j = 0 ∑ t − 1 ( j + 1 ) F j = t F t − j = 0 ∑ t − 1 F j = t F t − K t . Finally, since i ≥ 1 i \ge1 i ≥ 1 d i ≥ 0 d_i \ge0 d i ≥ 0 i i i W t = ∑ i = 1 t i d i ≥ ∑ i = 1 t d i = F t − F 0 = F t W_t = \sum_{i=1}^{t} id_i \ge\sum_{i=1}^{t} d_i = F_t-F_0=F_t W t = ∑ i = 1 t i d i ≥ ∑ i = 1 t d i = F t − F 0 = F t
Proof of Lemma 4.3
Proof. At first, we assume that the optimal base can be ordered as O = { o 1 , … , o r } O = \{o_1,\ldots,o_r\} O = { o 1 , … , o r } S t ∪ { o t + 1 , … , o r } S_t \cup\{o_{t+1},\ldots,o_r\} S t ∪ { o t + 1 , … , o r } t = 0 , … , r − 1 t=0,\ldots,r-1 t = 0 , … , r − 1 A = S i − 1 A=S_{i-1} A = S i − 1 C = S t ∪ { o i } C=S_t\cup\{o_i\} C = S t ∪ { o i } C ∖ A C\setminus A C ∖ A { s i , … , s t , o i } \{s_i,\ldots,s_t,o_i\} { s i , … , s t , o i } t − i + 2 t-i+2 t − i + 2 Lemma 4.2 shows that S i − 1 + o i ∈ I S_{i-1}+o_i\in\mathcal{I} S i − 1 + o i ∈ I o i o_i o i S i − 1 S_{i-1} S i − 1 j ≥ i j\ge i j ≥ i S i − 1 + s j ⊆ S j ∈ I S_{i-1}+s_j\subseteq S_j\in\mathcal{I} S i − 1 + s j ⊆ S j ∈ I S i − 1 + s j ∈ I S_{i-1}+s_j\in\mathcal{I} S i − 1 + s j ∈ I s j s_j s j S i − 1 S_{i-1} S i − 1 s i s_i s i i i i d i d_i d i
∑ e ∈ C ∖ A f ( e ∣ S i − 1 ) ≤ ( t − i + 2 ) d i . \sum_{e\in C\setminus A} f(e\mid S_{i-1})\le(t-i+2)d_i. e ∈ C ∖ A ∑ f ( e ∣ S i − 1 ) ≤ ( t − i + 2 ) d i . On the other hand, weak submodularity gives
γ ( f ( C ) − f ( A ) ) ≤ ∑ e ∈ C ∖ A f ( e ∣ S i − 1 ) , \gamma(f(C)-f(A))\le\sum_{e\in C\setminus A} f(e\mid S_{i-1}), γ ( f ( C ) − f ( A )) ≤ e ∈ C ∖ A ∑ f ( e ∣ S i − 1 ) , and the joint gain has the exact decomposition
f ( C ) − f ( A ) = F t − F i − 1 + f ( o i ∣ S t ) . f(C)-f(A)=F_t-F_{i-1}+f(o_i\mid S_t). f ( C ) − f ( A ) = F t − F i − 1 + f ( o i ∣ S t ) . Combining the last three displays gives
γ ( F t − F i − 1 + f ( o i ∣ S t ) ) ≤ ∑ e ∈ C ∖ A f ( e ∣ S i − 1 ) ≤ ( t − i + 2 ) d i . \gamma(F_t-F_{i-1}+f(o_i\mid S_t))\le\sum_{e\in C\setminus A} f(e\mid S_{i-1})\le(t-i+2)d_i. γ ( F t − F i − 1 + f ( o i ∣ S t )) ≤ e ∈ C ∖ A ∑ f ( e ∣ S i − 1 ) ≤ ( t − i + 2 ) d i . After subtracting γ ( F t − F i − 1 ) \gamma(F_t-F_{i-1}) γ ( F t − F i − 1 ) (25) .
Proof of Lemma 4.4
Proof. We first sum the results of Lemma 4.3, namely,
γ ∑ i = 1 t f ( o i ∣ S t ) ≤ ∑ i = 1 t ( ( t − i + 2 ) d i − γ ( F t − F i − 1 ) ) = ( t + 2 ) ∑ i = 1 t d i − ∑ i = 1 t i d i − γ ( t F t − ∑ i = 1 t F i − 1 ) = ( t + 2 ) F t − W t − γ ( t F t − K t ) = ( t + 2 ) F t − ( 1 + γ ) W t , (44) \begin{aligned}
\gamma\sum_{i=1}^{t}f(o_i\mid S_t)\le\sum_{i=1}^{t}\left((t-i+2)d_i-\gamma(F_t-F_{i-1})\right) \\
&= (t+2)\sum_{i=1}^{t}d_i-\sum_{i=1}^{t}id_i-\gamma\left(tF_t-\sum_{i=1}^{t}F_{i-1}\right) \\
&= (t+2)F_t-W_t-\gamma(tF_t-K_t)=(t+2)F_t-(1+\gamma)W_t, \tag*{(44)}
\end{aligned} γ i = 1 ∑ t f ( o i ∣ S t ) ≤ i = 1 ∑ t ( ( t − i + 2 ) d i − γ ( F t − F i − 1 ) ) = ( t + 2 ) i = 1 ∑ t d i − i = 1 ∑ t i d i − γ ( t F t − i = 1 ∑ t F i − 1 ) = ( t + 2 ) F t − W t − γ ( t F t − K t ) = ( t + 2 ) F t − ( 1 + γ ) W t , (44) where the final equality follows from t F t − K t = W t tF_t-K_t=W_t t F t − K t = W t Lemma 4.1 .
For every i > t i>t i > t Lemma 4.2 shows that o i o_i o i S t S_t S t t + 1 t+1 t + 1 d t + 1 d_{t+1} d t + 1 t < r t<r t < r
∑ i = t + 1 r f ( o i ∣ S t ) ≤ ( r − t ) d t + 1 . (45) \sum_{i=t+1}^{r} f(o_i\mid S_t)\le(r-t)d_{t+1}. \tag*{(45)} i = t + 1 ∑ r f ( o i ∣ S t ) ≤ ( r − t ) d t + 1 . (45) Moreover, throughout weak submodularity, we have
∑ i = 1 r f ( o i ∣ S t ) ≥ γ ( f ( S t ∪ O ) − F t ) ≥ γ ( O P T − F t ) . \sum_{i=1}^{r} f(o_i\mid S_t)\ge\gamma\left(f(S_t\cup O)-F_t\right)\ge\gamma(\mathrm{OPT}-F_t). i = 1 ∑ r f ( o i ∣ S t ) ≥ γ ( f ( S t ∪ O ) − F t ) ≥ γ ( OPT − F t ) . Therefore, for 1 ≤ t ≤ r 1\le t\le r 1 ≤ t ≤ r (44) and Eq. (45) imply
γ 2 ( O P T − F t ) ≤ γ ∑ i = 1 t f ( o i ∣ S t ) + γ ∑ i = t + 1 r f ( o i ∣ S t ) ≤ ( t + 2 ) F t − ( 1 + γ ) W t + γ ( r − t ) d t + 1 . \begin{aligned}
\gamma^2(\mathrm{OPT}-F_t)\le\gamma\sum_{i=1}^{t}f(o_i\mid S_t)+\gamma\sum_{i=t+1}^{r}f(o_i\mid S_t) \\
&\le(t+2)F_t-(1+\gamma)W_t+\gamma(r-t)d_{t+1}.
\end{aligned} γ 2 ( OPT − F t ) ≤ γ i = 1 ∑ t f ( o i ∣ S t ) + γ i = t + 1 ∑ r f ( o i ∣ S t ) ≤ ( t + 2 ) F t − ( 1 + γ ) W t + γ ( r − t ) d t + 1 . After adding γ 2 F t \gamma^2F_t γ 2 F t
γ 2 O P T ≤ ( t + 2 + γ 2 ) F t − ( 1 + γ ) W t + γ ( r − t ) d t + 1 = ( 2 − γ + γ 2 ) F t + ( t F t − W t ) + γ ( F t − W t ) + γ ( r − t ) d t + 1 = B γ F t + K t − γ ( W t − F t ) + γ ( r − t ) d t + 1 ≤ B γ F t + K t + γ ( r − t ) d t + 1 , \begin{aligned}
\gamma^2\mathrm{OPT}\le(t+2+\gamma^2)F_t-(1+\gamma)W_t+\gamma(r-t)d_{t+1} \\
&= (2-\gamma+\gamma^2)F_t+(tF_t-W_t)+\gamma(F_t-W_t)+\gamma(r-t)d_{t+1} \\
&= B_\gamma F_t+K_t-\gamma(W_t-F_t)+\gamma(r-t)d_{t+1}\le B_\gamma F_t+K_t+\gamma(r-t)d_{t+1},
\end{aligned} γ 2 OPT ≤ ( t + 2 + γ 2 ) F t − ( 1 + γ ) W t + γ ( r − t ) d t + 1 = ( 2 − γ + γ 2 ) F t + ( t F t − W t ) + γ ( F t − W t ) + γ ( r − t ) d t + 1 = B γ F t + K t − γ ( W t − F t ) + γ ( r − t ) d t + 1 ≤ B γ F t + K t + γ ( r − t ) d t + 1 , where the final inequality follows from W t ≥ F t W_t\ge F_t W t ≥ F t Lemma 4.1 . Thus, we prove Eq. (26) for 1 ≤ t ≤ r 1\le t\le r 1 ≤ t ≤ r t = r t=r t = r
γ 2 O P T ≤ B γ F r + K r , \gamma^2\mathrm{OPT}\le B_\gamma F_r+K_r, γ 2 OPT ≤ B γ F r + K r , which proves Eq. (27) . Finally, at t = 0 t=0 t = 0
γ O P T ≤ ∑ o ∈ O f ( o ∣ ∅ ) ≤ r d 1 . \gamma\mathrm{OPT}\le\sum_{o\in O}f(o\mid\varnothing)\le rd_1. γ OPT ≤ o ∈ O ∑ f ( o ∣ ∅ ) ≤ r d 1 . Multiplying by γ \gamma γ (26) for t = 0 t=0 t = 0 f ( ∅ ) = 0 f(\varnothing)=0 f ( ∅ ) = 0
Proof of Lemma 4.5
Proof. Set V = C − B M V=C-BM V = C − B M V ≤ 0 V\le0 V ≤ 0 C ≤ B M ≤ ( B + A ( 1 − 1 / r ) ) M C\le BM\le\left(B+\sqrt{A(1-1/r)}\right)M C ≤ B M ≤ ( B + A ( 1 − 1/ r ) ) M V > 0 V>0 V > 0 C ≤ B M + K r C\le BM+K_r C ≤ B M + K r K r ≥ V K_r\ge V K r ≥ V h h h K h ≥ V K_h\ge V K h ≥ V t < h t<h t < h
V − K t = C − B M − K t ≤ A ( F t + 1 − F t ) + B ( F t − M ) ≤ A ( F t + 1 − F t ) . V-K_t=C-BM-K_t\le A(F_{t+1}-F_t)+B(F_t-M)\le A(F_{t+1}-F_t). V − K t = C − B M − K t ≤ A ( F t + 1 − F t ) + B ( F t − M ) ≤ A ( F t + 1 − F t ) . Since K t < V K_t<V K t < V t < h t<h t < h F t ≥ 0 F_t\ge0 F t ≥ 0
∑ t = 0 h − 1 ( V − K t ) F t ≤ A ∑ t = 0 h − 1 F t ( F t + 1 − F t ) . (46) \sum_{t=0}^{h-1}(V-K_t)F_t\le A\sum_{t=0}^{h-1}F_t(F_{t+1}-F_t). \tag*{(46)} t = 0 ∑ h − 1 ( V − K t ) F t ≤ A t = 0 ∑ h − 1 F t ( F t + 1 − F t ) . (46) Moreover, due to K t + 1 = K t + F t K_{t+1}=K_t+F_t K t + 1 = K t + F t K t + 1 2 − K t 2 = 2 K t F t + F t 2 K_{t+1}^2-K_t^2=2K_tF_t+F_t^2 K t + 1 2 − K t 2 = 2 K t F t + F t 2
∑ t < h K t F t = 1 2 ( K h 2 − ∑ t < h F t 2 ) . \sum_{t<h} K_tF_t=\frac{1}{2}\left(K_h^2-\sum_{t<h}F_t^2\right). t < h ∑ K t F t = 2 1 ( K h 2 − t < h ∑ F t 2 ) . Consequently,
∑ t < h ( V − K t ) F t = V K h − 1 2 K h 2 + 1 2 ∑ t < h F t 2 = 1 2 V 2 − 1 2 ( K h − V ) 2 + 1 2 ∑ t < h F t 2 . \sum_{t<h}(V-K_t)F_t=VK_h-\frac{1}{2}K_h^2+\frac{1}{2}\sum_{t<h}F_t^2=\frac{1}{2}V^2-\frac{1}{2}(K_h-V)^2+\frac{1}{2}\sum_{t<h}F_t^2. t < h ∑ ( V − K t ) F t = V K h − 2 1 K h 2 + 2 1 t < h ∑ F t 2 = 2 1 V 2 − 2 1 ( K h − V ) 2 + 2 1 t < h ∑ F t 2 . The minimality of h h h K h − 1 < V ≤ K h = K h − 1 + F h − 1 K_{h-1}<V\leq K_h=K_{h-1}+F_{h-1} K h − 1 < V ≤ K h = K h − 1 + F h − 1 0 ≤ K h − V ≤ F h − 1 0\leq K_h-V\leq F_{h-1} 0 ≤ K h − V ≤ F h − 1 ( K h − V ) 2 ≤ F h − 1 2 ≤ ∑ t < h F t 2 (K_h-V)^2\leq F_{h-1}^2\leq\sum_{t<h}F_t^2 ( K h − V ) 2 ≤ F h − 1 2 ≤ ∑ t < h F t 2
∑ t < h ( V − K t ) F t = 1 2 V 2 + 1 2 ( ∑ t < h F t 2 − ( K h − V ) 2 ) ≥ 1 2 V 2 . (47) \sum_{t<h}(V-K_t)F_t=\frac{1}{2}V^2+\frac{1}{2}\left(\sum_{t<h}F_t^2-(K_h-V)^2\right)\geq\frac{1}{2}V^2. \tag*{(47)} t < h ∑ ( V − K t ) F t = 2 1 V 2 + 2 1 ( t < h ∑ F t 2 − ( K h − V ) 2 ) ≥ 2 1 V 2 . (47) Next, we investigate the right-hand side of Eq. (46) . Due to d t + 1 ≜ F t + 1 − F t d_{t+1}\triangleq F_{t+1}-F_t d t + 1 ≜ F t + 1 − F t 2 F t d t + 1 = F t + 1 2 − F t 2 − d t + 1 2 2F_td_{t+1}=F_{t+1}^2-F_t^2-d_{t+1}^2 2 F t d t + 1 = F t + 1 2 − F t 2 − d t + 1 2 t = 0 , … , h − 1 t=0,\ldots,h-1 t = 0 , … , h − 1 F 0 = 0 F_0=0 F 0 = 0
A ∑ t < h F t ( F t + 1 − F t ) = A ∑ t < h F t d t + 1 = A 2 ( ∑ t < h ( F t + 1 2 − F t 2 ) − ∑ t < h d t + 1 2 ) = A 2 ( F h 2 − ∑ t < h d t + 1 2 ) ≤ A 2 ( 1 − 1 h ) F h 2 ≤ A 2 ( 1 − 1 r ) M 2 , \begin{aligned}
A\sum_{t<h}F_t(F_{t+1}-F_t)=A\sum_{t<h}F_td_{t+1}=\frac{A}{2}\left(\sum_{t<h}(F_{t+1}^2-F_t^2)-\sum_{t<h}d_{t+1}^2\right) \\
&=\frac{A}{2}\left(F_h^2-\sum_{t<h}d_{t+1}^2\right)\leq\frac{A}{2}\left(1-\frac{1}{h}\right)F_h^2\leq\frac{A}{2}\left(1-\frac{1}{r}\right)M^2,
\end{aligned} A t < h ∑ F t ( F t + 1 − F t ) = A t < h ∑ F t d t + 1 = 2 A ( t < h ∑ ( F t + 1 2 − F t 2 ) − t < h ∑ d t + 1 2 ) = 2 A ( F h 2 − t < h ∑ d t + 1 2 ) ≤ 2 A ( 1 − h 1 ) F h 2 ≤ 2 A ( 1 − r 1 ) M 2 , where the first inequality follows from the Cauchy-Schwarz inequality ∑ t < h d t + 1 2 ≥ 1 h ( ∑ t < h d t + 1 ) 2 = F h 2 h \sum_{t<h}d_{t+1}^2\geq\frac{1}{h}\left(\sum_{t<h}d_{t+1}\right)^2=\frac{F_h^2}{h} ∑ t < h d t + 1 2 ≥ h 1 ( ∑ t < h d t + 1 ) 2 = h F h 2 F h ≤ M F_h\leq M F h ≤ M
A ∑ t < h F t ( F t + 1 − F t ) ≤ A 2 ( 1 − 1 r ) M 2 . (48) A\sum_{t<h}F_t(F_{t+1}-F_t)\leq\frac{A}{2}\left(1-\frac{1}{r}\right)M^2. \tag*{(48)} A t < h ∑ F t ( F t + 1 − F t ) ≤ 2 A ( 1 − r 1 ) M 2 . (48) Merging Eq. (47) and Eq. (48) into Eq. (46) , we obtain
1 2 V 2 ≤ ∑ t < h ( V − K t ) F t ≤ A ∑ t < h F t ( F t + 1 − F t ) ≤ A 2 ( 1 − 1 r ) M 2 . \frac{1}{2}V^2\leq\sum_{t<h}(V-K_t)F_t\leq A\sum_{t<h}F_t(F_{t+1}-F_t)\leq\frac{A}{2}\left(1-\frac{1}{r}\right)M^2. 2 1 V 2 ≤ t < h ∑ ( V − K t ) F t ≤ A t < h ∑ F t ( F t + 1 − F t ) ≤ 2 A ( 1 − r 1 ) M 2 . Therefore V = C − B M ≤ A ( 1 − 1 / r ) M V=C-BM\leq\sqrt{A(1-1/r)}M V = C − B M ≤ A ( 1 − 1/ r ) M (28) .
Proof of the rank-dependent terms in Theorem 4.6.
Proof. In this section, we show the verification on Theorem 4.6 . At first, we set
A ≜ γ r , B ≜ B γ , C ≜ γ 2 O P T , M ≜ F r . A\triangleq\gamma r,\qquad B\triangleq B_\gamma,\qquad C\triangleq\gamma^2\mathrm{OPT},\qquad M\triangleq F_r. A ≜ γ r , B ≜ B γ , C ≜ γ 2 OPT , M ≜ F r . Lemma 4.1 shows that 0 = F 0 ≤ F 1 ≤ ⋯ ≤ F r = M 0=F_0\leq F_1\leq\cdots\leq F_r=M 0 = F 0 ≤ F 1 ≤ ⋯ ≤ F r = M t < r t<r t < r Lemma 4.4 gives
C ≤ B γ F t + K t + γ ( r − t ) ( F t + 1 − F t ) ≤ B F t + K t + A ( F t + 1 − F t ) , C\leq B_\gamma F_t+K_t+\gamma(r-t)(F_{t+1}-F_t)\leq BF_t+K_t+A(F_{t+1}-F_t), C ≤ B γ F t + K t + γ ( r − t ) ( F t + 1 − F t ) ≤ B F t + K t + A ( F t + 1 − F t ) , where the second inequality uses γ ( r − t ) ≤ A \gamma(r-t) \le A γ ( r − t ) ≤ A C ≤ B M + K r C \le BM + K_r C ≤ B M + K r (27) . Thus, by Lemma 4.5, we have yields
γ 2 O P T ≤ ( B γ + γ r ( 1 − 1 / r ) ) F r = ( B γ + γ ( r − 1 ) ) F r . \gamma^2\mathrm{OPT} \le\left(B_\gamma+\sqrt{\gamma r(1-1/r)}\right)F_r=\left(B_\gamma+\sqrt{\gamma(r-1)}\right)F_r. γ 2 OPT ≤ ( B γ + γ r ( 1 − 1/ r ) ) F r = ( B γ + γ ( r − 1 ) ) F r . Consequently, F r O P T ≥ γ 2 B γ + γ ( r − 1 ) \frac{F_r}{\mathrm{OPT}} \ge\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}} OPT F r ≥ B γ + γ ( r − 1 ) γ 2
Moreover, every element of O O O F 1 F_1 F 1
r F 1 ≥ ∑ o ∈ O f ( o ∣ ∅ ) ≥ γ O P T , rF_1 \ge\sum_{o\in O}f(o\mid\varnothing)\ge\gamma\mathrm{OPT}, r F 1 ≥ o ∈ O ∑ f ( o ∣ ∅ ) ≥ γ OPT , where the second inequality follows from weak submodularity applied to ∅ ⊆ O \varnothing\subseteq O ∅ ⊆ O F r O P T ≥ F 1 O P T ≥ γ / r \frac{F_r}{\mathrm{OPT}}\ge\frac{F_1}{\mathrm{OPT}}\ge\gamma/r OPT F r ≥ OPT F 1 ≥ γ / r (29) . □
Proof of Theorem 4.7
Proof. Firstly, for any set A A A s , e ∉ A s,e\notin A s , e ∈ / A γ \gamma γ
f ( s ∣ A ) + f ( e ∣ A ) ≥ γ ( f ( A + s + e ) − f ( A ) ) = γ ( f ( s ∣ A ) + f ( e ∣ A + s ) ) . f(s\mid A)+f(e\mid A)\ge\gamma\bigl(f(A+s+e)-f(A)\bigr)=\gamma\bigl(f(s\mid A)+f(e\mid A+s)\bigr). f ( s ∣ A ) + f ( e ∣ A ) ≥ γ ( f ( A + s + e ) − f ( A ) ) = γ ( f ( s ∣ A ) + f ( e ∣ A + s ) ) . Then, if γ > 0 \gamma>0 γ > 0
f ( e ∣ A + s ) ≤ γ − 1 f ( e ∣ A ) + 1 − γ γ f ( s ∣ A ) . (49) f(e\mid A+s)\le\gamma^{-1}f(e\mid A)+\frac{1-\gamma}{\gamma}f(s\mid A). \tag*{(49)} f ( e ∣ A + s ) ≤ γ − 1 f ( e ∣ A ) + γ 1 − γ f ( s ∣ A ) . (49) Let O = { o 1 , … , o r } O=\{o_1,\ldots,o_r\} O = { o 1 , … , o r } f ( o i ∣ S r ) f(o_i\mid S_r) f ( o i ∣ S r ) i ∈ [ r ] i\in[r] i ∈ [ r ] o i ∈ S r o_i\in S_r o i ∈ S r f ( o i ∣ S r ) = 0 f(o_i\mid S_r)=0 f ( o i ∣ S r ) = 0 o i ∉ S r o_i\notin S_r o i ∈ / S r
x t ≜ f ( o i ∣ S t ) , t = i − 1 , i , … , r . x_t\triangleq f(o_i\mid S_t),\qquad t=i-1,i,\ldots,r. x t ≜ f ( o i ∣ S t ) , t = i − 1 , i , … , r . Lemma 4.2 shows that o i o_i o i S i − 1 S_{i-1} S i − 1 i i i
x i − 1 = f ( o i ∣ S i − 1 ) ≤ d i . (50) x_{i-1}=f(o_i\mid S_{i-1})\le d_i. \tag*{(50)} x i − 1 = f ( o i ∣ S i − 1 ) ≤ d i . (50) Then, for each t = i , … , r t=i,\ldots,r t = i , … , r (49) with A = S t − 1 A=S_{t-1} A = S t − 1 s = s t s=s_t s = s t e = o i e=o_i e = o i S t = S t − 1 + s t S_t=S_{t-1}+s_t S t = S t − 1 + s t f ( s t ∣ S t − 1 ) = d t f(s_t\mid S_{t-1})=d_t f ( s t ∣ S t − 1 ) = d t
x t ≤ γ − 1 x t − 1 + 1 − γ γ d t . (51) x_t\le\gamma^{-1}x_{t-1}+\frac{1-\gamma}{\gamma}d_t. \tag*{(51)} x t ≤ γ − 1 x t − 1 + γ 1 − γ d t . (51) We now iterate Eq. (51) . We can get, for any m = i , … , r m=i,\ldots,r m = i , … , r
x m ≤ γ − ( m − i + 1 ) d i + ( 1 − γ ) ∑ t = i m γ − ( m − t + 1 ) d t . (52) x_m\le\gamma^{-(m-i+1)}d_i+(1-\gamma)\sum_{t=i}^{m}\gamma^{-(m-t+1)}d_t. \tag*{(52)} x m ≤ γ − ( m − i + 1 ) d i + ( 1 − γ ) t = i ∑ m γ − ( m − t + 1 ) d t . (52) Taking m = r m=r m = r i i i
f ( o i ∣ S r ) ≤ γ − ( r − i + 1 ) d i + ( 1 − γ ) ∑ t = i r γ − ( r − t + 1 ) d t . (53) f(o_i\mid S_r)\le\gamma^{-(r-i+1)}d_i+(1-\gamma)\sum_{t=i}^{r}\gamma^{-(r-t+1)}d_t. \tag*{(53)} f ( o i ∣ S r ) ≤ γ − ( r − i + 1 ) d i + ( 1 − γ ) t = i ∑ r γ − ( r − t + 1 ) d t . (53) We sum Eq. (53) over i = 1 , … , r i=1,\ldots,r i = 1 , … , r t t t γ − ( r − t + 1 ) d t \gamma^{-(r-t+1)}d_t γ − ( r − t + 1 ) d t (53) , d t d_t d t i = 1 , … , t i=1,\ldots,t i = 1 , … , t t ( 1 − γ ) γ − ( r − t + 1 ) d t t(1-\gamma)\gamma^{-(r-t+1)}d_t t ( 1 − γ ) γ − ( r − t + 1 ) d t
∑ i = 1 r f ( o i ∣ S r ) ≤ ∑ t = 1 r γ − ( r − t + 1 ) [ 1 + t ( 1 − γ ) ] d t . (54) \sum_{i=1}^{r} f(o_i\mid S_r) \le\sum_{t=1}^{r}\gamma^{-(r-t+1)}\left[1+t(1-\gamma)\right]d_t. \tag*{(54)} i = 1 ∑ r f ( o i ∣ S r ) ≤ t = 1 ∑ r γ − ( r − t + 1 ) [ 1 + t ( 1 − γ ) ] d t . (54) It remains to bound the coefficient of each d t d_t d t a t = γ − ( r − t + 1 ) ( 1 + t ( 1 − γ ) ) a_t=\gamma^{-(r-t+1)}\left(1+t(1-\gamma)\right) a t = γ − ( r − t + 1 ) ( 1 + t ( 1 − γ ) ) a t a_t a t
a t + 1 a t = 1 − ( t + 1 ) ( 1 − γ ) 2 1 + t ( 1 − γ ) ≤ 1. \frac{a_{t+1}}{a_t}=1-\frac{(t+1)(1-\gamma)^2}{1+t(1-\gamma)}\le1. a t a t + 1 = 1 − 1 + t ( 1 − γ ) ( t + 1 ) ( 1 − γ ) 2 ≤ 1. Thus a t ≤ a 1 = γ − r ( 2 − γ ) a_t\le a_1=\gamma^{-r}(2-\gamma) a t ≤ a 1 = γ − r ( 2 − γ )
∑ i = 1 r f ( o i ∣ S r ) ≤ ( 2 − γ ) γ − r ∑ t = 1 r d t = ( 2 − γ ) γ − r F r . (55) \sum_{i=1}^{r} f(o_i\mid S_r)\le(2-\gamma)\gamma^{-r}\sum_{t=1}^{r}d_t=(2-\gamma)\gamma^{-r}F_r. \tag*{(55)} i = 1 ∑ r f ( o i ∣ S r ) ≤ ( 2 − γ ) γ − r t = 1 ∑ r d t = ( 2 − γ ) γ − r F r . (55) Finally, γ \gamma γ
γ ( O P T − F r ) ≤ γ ( f ( S r ∪ O ) − F r ) ≤ ∑ o ∈ O ∖ S r f ( o ∣ S r ) = ∑ i = 1 r f ( o i ∣ S r ) . \gamma(\mathrm{OPT}-F_r)\le\gamma\left(f(S_r\cup O)-F_r\right)\le\sum_{o\in O\setminus S_r}f(o\mid S_r)=\sum_{i=1}^{r}f(o_i\mid S_r). γ ( OPT − F r ) ≤ γ ( f ( S r ∪ O ) − F r ) ≤ o ∈ O ∖ S r ∑ f ( o ∣ S r ) = i = 1 ∑ r f ( o i ∣ S r ) . Combining this inequality with Eq. (55) yields γ ( O P T − F r ) ≤ ( 2 − γ ) γ − r F r \gamma(\mathrm{OPT}-F_r)\le(2-\gamma)\gamma^{-r}F_r γ ( OPT − F r ) ≤ ( 2 − γ ) γ − r F r
F r O P T ≥ γ ( 2 − γ ) γ − r + γ = γ r + 1 2 − γ + γ r + 1 , \frac{F_r}{\mathrm{OPT}}\ge\frac{\gamma}{(2-\gamma)\gamma^{-r}+\gamma}=\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}, OPT F r ≥ ( 2 − γ ) γ − r + γ γ = 2 − γ + γ r + 1 γ r + 1 , which proves Eq. (30) .
Proof of Lemma 4.8
Proof. Set x ≔ γ r x\coloneqq\sqrt{\gamma^r} x : = γ r B γ = 2 − γ + γ 2 ≤ 2 B_\gamma=2-\gamma+\gamma^2\le2 B γ = 2 − γ + γ 2 ≤ 2 γ ( r − 1 ) < γ r = x \sqrt{\gamma(r-1)}<\sqrt{\gamma^r}=x γ ( r − 1 ) < γ r = x
B γ + γ ( r − 1 ) < 2 + x < 2 + 2 x + γ 2 . B_\gamma+\sqrt{\gamma(r-1)}<2+x<2+2x+\gamma^2. B γ + γ ( r − 1 ) < 2 + x < 2 + 2 x + γ 2 . This proves the first strict inequality in Eq. (32) .
For the second one, it is worth noting that, when r ≥ 2 r\ge2 r ≥ 2 x ≥ 2 γ > γ x\ge\sqrt{2\gamma}>\gamma x ≥ 2 γ > γ
1 2 ( 1 + x ) > 1 2 ( 1 + γ ) ≥ γ ≥ γ 2 , \frac{1}{2}(1+x)>\frac{1}{2}(1+\gamma)\ge\gamma\ge\gamma^2, 2 1 ( 1 + x ) > 2 1 ( 1 + γ ) ≥ γ ≥ γ 2 , and hence
γ 2 2 + 2 x + γ 2 > γ 2 2 + 2 x + 1 2 ( 1 + x ) = γ 2 5 2 ( 1 + x ) = 0.4 γ 2 1 + x . \frac{\gamma^2}{2+2x+\gamma^2}>\frac{\gamma^2}{2+2x+\frac{1}{2}(1+x)}=\frac{\gamma^2}{\frac{5}{2}(1+x)}=\frac{0.4\gamma^2}{1+x}. 2 + 2 x + γ 2 γ 2 > 2 + 2 x + 2 1 ( 1 + x ) γ 2 = 2 5 ( 1 + x ) γ 2 = 1 + x 0.4 γ 2 . Proof of Lemma 4.9
In this section, we prove Lemma 4.9 . Before that, we first give a refined result analogous to Lemma 4.3 , that is to say,
Lemma B.1. For any $1/2 \le \gamma < 1a n d $ 1 ≤ i ≤ t ≤ r and \$1 \le i \le t \le r an d $1 ≤ i ≤ t ≤ r
γ f ( o i ∣ S t ) ≤ 15 ( 3 + ( 1 − γ ) ( t − i + 1 ) ) d i . (56) \gamma f(o_i \mid S_t) \le15\bigl(3 + (1-\gamma)(t-i+1)\bigr)d_i. \tag*{(56)} γ f ( o i ∣ S t ) ≤ 15 ( 3 + ( 1 − γ ) ( t − i + 1 ) ) d i . (56) With the help of Eq. (56) , we then verify Lemma 4.9 , that is to say,
Proof. For any 1 ≤ t ≤ r 1 \le t \le r 1 ≤ t ≤ r (56) over i = 1 , … , t i=1,\ldots,t i = 1 , … , t
γ ∑ i = 1 t f ( o i ∣ S t ) ≤ 45 ∑ i = 1 t d i + 15 ( 1 − γ ) ∑ i = 1 t ( t − i + 1 ) d i = 45 ∑ i = 1 t d i + 15 ( 1 − γ ) ( ( t + 1 ) ∑ i = 1 t d i − ∑ i = 1 t i d i ) = 45 F t + 15 ( 1 − γ ) ( ( t + 1 ) F t − W t ) = 45 F t + 15 ( 1 − γ ) ( F t + K t ) = ( 45 + 15 ( 1 − γ ) ) F t + 15 ( 1 − γ ) K t , \begin{aligned}
\gamma\sum_{i=1}^{t} f(o_i \mid S_t) \le45 \sum_{i=1}^{t} d_i + 15(1-\gamma) \sum_{i=1}^{t}(t-i+1)d_i \\
&=45\sum_{i=1}^{t}d_i+15(1-\gamma)\left((t+1)\sum_{i=1}^{t}d_i-\sum_{i=1}^{t}id_i\right) \\
&=45F_t+15(1-\gamma)\left((t+1)F_t-W_t\right) \\
&=45F_t+15(1-\gamma)(F_t+K_t)=(45+15(1-\gamma))F_t+15(1-\gamma)K_t,
\end{aligned} γ i = 1 ∑ t f ( o i ∣ S t ) ≤ 45 i = 1 ∑ t d i + 15 ( 1 − γ ) i = 1 ∑ t ( t − i + 1 ) d i = 45 i = 1 ∑ t d i + 15 ( 1 − γ ) ( ( t + 1 ) i = 1 ∑ t d i − i = 1 ∑ t i d i ) = 45 F t + 15 ( 1 − γ ) ( ( t + 1 ) F t − W t ) = 45 F t + 15 ( 1 − γ ) ( F t + K t ) = ( 45 + 15 ( 1 − γ )) F t + 15 ( 1 − γ ) K t , where the third equality comes from W t = t F t − K t W_t=tF_t-K_t W t = t F t − K t Lemma 4.1 . For every i > t i>t i > t Lemma 4.2 shows that o i o_i o i S t S_t S t t + 1 t+1 t + 1 d t + 1 d_{t+1} d t + 1 t < r t<r t < r
∑ i = t + 1 r f ( o i ∣ S t ) ≤ ( r − t ) d t + 1 . \sum_{i=t+1}^{r}f(o_i \mid S_t)\le(r-t)d_{t+1}. i = t + 1 ∑ r f ( o i ∣ S t ) ≤ ( r − t ) d t + 1 . As a result, we have
γ 2 ( O P T − F t ) ≤ γ ∑ i = 1 r f ( o i ∣ S t ) ≤ ( 45 + 15 ( 1 − γ ) ) F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 . \gamma^2(\mathrm{OPT}-F_t)\le\gamma\sum_{i=1}^{r}f(o_i \mid S_t)\le(45+15(1-\gamma))F_t+15(1-\gamma)K_t+\gamma(r-t)d_{t+1}. γ 2 ( OPT − F t ) ≤ γ i = 1 ∑ r f ( o i ∣ S t ) ≤ ( 45 + 15 ( 1 − γ )) F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 . After adding γ 2 F t \gamma^2F_t γ 2 F t
γ 2 O P T ≤ ( γ 2 + 45 + 15 ( 1 − γ ) ) F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 = D γ F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 , \begin{aligned}
\gamma^2\mathrm{OPT}\le(\gamma^2+45+15(1-\gamma))F_t+15(1-\gamma)K_t+\gamma(r-t)d_{t+1} \\
&=D_\gamma F_t+15(1-\gamma)K_t+\gamma(r-t)d_{t+1},
\end{aligned} γ 2 OPT ≤ ( γ 2 + 45 + 15 ( 1 − γ )) F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 = D γ F t + 15 ( 1 − γ ) K t + γ ( r − t ) d t + 1 , where γ 2 + 45 + 15 ( 1 − γ ) = 60 − 15 γ + γ 2 = D γ \gamma^2+45+15(1-\gamma)=60-15\gamma+\gamma^2=D_\gamma γ 2 + 45 + 15 ( 1 − γ ) = 60 − 15 γ + γ 2 = D γ t = r t=r t = r
γ 2 O P T ≤ D γ F r + 15 ( 1 − γ ) K r , \gamma^2\mathrm{OPT}\le D_\gamma F_r+15(1-\gamma)K_r, γ 2 OPT ≤ D γ F r + 15 ( 1 − γ ) K r , which is Eq. (34) . ∎
In the remainder of this section, we show the proof of Lemma B.1 .
Proof of Lemma B.1
Proof. Fix $1 \le i \le t \le r$. If o i ∈ S t o_i \in S_t o i ∈ S t f ( o i ∣ S t ) = 0 f(o_i \mid S_t) = 0 f ( o i ∣ S t ) = 0 Lemma B.1 immediately follows. Thus, we suppose that o i ∉ S t o_i \notin S_t o i ∈ / S t
h ≜ t − i + 1 , x ℓ ≜ f ( o i ∣ S i − 1 + ℓ ) ( 0 ≤ ℓ ≤ h ) . h \triangleq t-i+1,\qquad x_\ell\triangleq f(o_i \mid S_{i-1+\ell})\quad(0 \le\ell\le h). h ≜ t − i + 1 , x ℓ ≜ f ( o i ∣ S i − 1 + ℓ ) ( 0 ≤ ℓ ≤ h ) . Moreover, Lemma 4.2 shows that o i o_i o i S i − 1 S_{i-1} S i − 1 i i i
x 0 ≤ d i . (57) x_0 \le d_i. \tag*{(57)} x 0 ≤ d i . (57) Next, for any $0 \le u < v \le h$, we apply γ \gamma γ A = S i − 1 + u A=S_{i-1+u} A = S i − 1 + u C = S i − 1 + v ∪ { o i } C=S_{i-1+v}\cup\{o_i\} C = S i − 1 + v ∪ { o i }
∑ e ∈ C ∖ A f ( e ∣ A ) ≥ γ ( f ( C ) − f ( A ) ) . \sum_{e\in C\setminus A} f(e\mid A)\ge\gamma\left(f(C)-f(A)\right). e ∈ C ∖ A ∑ f ( e ∣ A ) ≥ γ ( f ( C ) − f ( A ) ) . Importantly, we know that, C ∖ A = { s i + u , … , s i + v − 1 } ∪ { o i } C\setminus A=\{s_{i+u},\ldots,s_{i+v-1}\}\cup\{o_i\} C ∖ A = { s i + u , … , s i + v − 1 } ∪ { o i } j ∈ { u + 1 , … , v } j\in\{u+1,\ldots,v\} j ∈ { u + 1 , … , v } s i + j − 1 s_{i+j-1} s i + j − 1 A A A A + s i + j − 1 ⊆ S i + j − 1 ∈ I A+s_{i+j-1}\subseteq S_{i+j-1}\in\mathcal{I} A + s i + j − 1 ⊆ S i + j − 1 ∈ I f ( s i + j − 1 ∣ A ) ≤ d i + u f(s_{i+j-1}\mid A)\le d_{i+u} f ( s i + j − 1 ∣ A ) ≤ d i + u u + 1 ≤ j ≤ v u+1\le j\le v u + 1 ≤ j ≤ v
∑ e ∈ C ∖ A f ( e ∣ A ) = f ( o i ∣ S i − 1 + u ) + ∑ j = u + 1 v f ( s i + j − 1 ∣ S i − 1 + u ) ≤ x u + ( v − u ) d i + u . \sum_{e\in C\setminus A}f(e\mid A)=f(o_i\mid S_{i-1+u})+\sum_{j=u+1}^{v}f(s_{i+j-1}\mid S_{i-1+u})\le x_u+(v-u)d_{i+u}. e ∈ C ∖ A ∑ f ( e ∣ A ) = f ( o i ∣ S i − 1 + u ) + j = u + 1 ∑ v f ( s i + j − 1 ∣ S i − 1 + u ) ≤ x u + ( v − u ) d i + u . Similarly, the joint gain f ( C ) − f ( A ) f(C)-f(A) f ( C ) − f ( A )
f ( C ) − f ( A ) = f ( o i ∣ S i − 1 + v ) + ∑ j = u + 1 v d i + j − 1 = x v + ∑ j = u + 1 v d i + j − 1 . f(C)-f(A)=f(o_i\mid S_{i-1+v})+\sum_{j=u+1}^{v}d_{i+j-1}=x_v+\sum_{j=u+1}^{v}d_{i+j-1}. f ( C ) − f ( A ) = f ( o i ∣ S i − 1 + v ) + j = u + 1 ∑ v d i + j − 1 = x v + j = u + 1 ∑ v d i + j − 1 . Hence
x u + ( v − u ) d i + u ≥ γ ( x v + ∑ j = u + 1 v d i + j − 1 ) , x_u+(v-u)d_{i+u}\ge\gamma\left(x_v+\sum_{j=u+1}^{v}d_{i+j-1}\right), x u + ( v − u ) d i + u ≥ γ ( x v + j = u + 1 ∑ v d i + j − 1 ) , or equivalently,
γ x v − x u + γ ∑ j = u + 1 v d i + j − 1 − ( v − u ) d i + u ≤ 0. (58) \gamma x_v-x_u+\gamma\sum_{j=u+1}^{v}d_{i+j-1}-(v-u)d_{i+u}\le0. \tag*{(58)} γ x v − x u + γ j = u + 1 ∑ v d i + j − 1 − ( v − u ) d i + u ≤ 0. (58) In the remainder of this section, we will construct a nonnegative linear combination of instances of Eq. (58) , indexed by suitable choices of u u u v v v x 1 , … , x h − 1 x_1,\ldots,x_{h-1} x 1 , … , x h − 1 d i + 1 , … , d i + h − 1 d_{i+1},\ldots,d_{i+h-1} d i + 1 , … , d i + h − 1 x 0 x_0 x 0 x h x_h x h d i d_i d i
Weight construction and coefficient cancellation. Before going into the details, we first define some useful symbols, namely,
M ≜ 3 + ( 1 − γ ) h , z ≜ 1 + 1 − γ M , ρ ≜ z − 1 , L ≜ ⌈ 5 M ⌉ , G ≜ ∑ a = 0 L − 1 z a . M\triangleq3+(1-\gamma)h,\qquad z\triangleq1+\frac{1-\gamma}{M},\qquad\rho\triangleq z^{-1},\qquad L\triangleq\lceil5M\rceil,\qquad G\triangleq\sum_{a=0}^{L-1}z^a. M ≜ 3 + ( 1 − γ ) h , z ≜ 1 + M 1 − γ , ρ ≜ z − 1 , L ≜ ⌈ 5 M ⌉ , G ≜ a = 0 ∑ L − 1 z a . With these notations, we next show two frequently used results, i.e., γ G ≥ L \gamma G \ge L γ G ≥ L γ z L ≥ 1 \gamma z^{L} \ge1 γ z L ≥ 1
G = ∑ a = 0 L − 1 ( 1 + 1 − γ M ) a ≥ ∑ a = 0 L − 1 ( 1 + a ( 1 − γ ) M ) = L ( 1 + ( 1 − γ ) ( L − 1 ) 2 M ) ≥ L ( 1 + ( 1 − γ ) ( 5 M − 1 ) 2 M ) = L ( 1 + ( 1 − γ ) ( 5 2 − 1 2 M ) ) ≥ L ( 1 + ( 1 − γ ) 1 γ ) = L γ . \begin{aligned}
G &= \sum_{a=0}^{L-1}\left(1+\frac{1-\gamma}{M}\right)^a \ge\sum_{a=0}^{L-1}\left(1+\frac{a(1-\gamma)}{M}\right) = L\left(1+\frac{(1-\gamma)(L-1)}{2M}\right) \\
&\ge L\left(1+\frac{(1-\gamma)(5M-1)}{2M}\right) = L\left(1+(1-\gamma)\left(\frac{5}{2}-\frac{1}{2M}\right)\right) \ge L\left(1+(1-\gamma)\frac{1}{\gamma}\right) = \frac{L}{\gamma}.
\end{aligned} G = a = 0 ∑ L − 1 ( 1 + M 1 − γ ) a ≥ a = 0 ∑ L − 1 ( 1 + M a ( 1 − γ ) ) = L ( 1 + 2 M ( 1 − γ ) ( L − 1 ) ) ≥ L ( 1 + 2 M ( 1 − γ ) ( 5 M − 1 ) ) = L ( 1 + ( 1 − γ ) ( 2 5 − 2 M 1 ) ) ≥ L ( 1 + ( 1 − γ ) γ 1 ) = γ L . where the first inequality follows from ( 1 + q ) a ≥ 1 + a q (1+q)^a \ge1+aq ( 1 + q ) a ≥ 1 + a q M ≥ 3 M \ge3 M ≥ 3 γ ≥ 1 / 2 \gamma\ge1/2 γ ≥ 1/2 5 2 − 1 2 M ≥ 7 3 ≥ 2 ≥ 1 γ \frac{5}{2}-\frac{1}{2M} \ge\frac{7}{3} \ge2 \ge\frac{1}{\gamma} 2 5 − 2 M 1 ≥ 3 7 ≥ 2 ≥ γ 1
After that, due to G = 1 − z L 1 − z G=\frac{1-z^L}{1-z} G = 1 − z 1 − z L
z L = 1 + ( z − 1 ) G = 1 + 1 − γ M G ≥ 1 + ( 1 − γ ) L γ M ≥ 1 + 1 − γ γ = 1 γ . z^L=1+(z-1)G=1+\frac{1-\gamma}{M}G\ge1+\frac{(1-\gamma)L}{\gamma M}\ge1+\frac{1-\gamma}{\gamma}=\frac{1}{\gamma}. z L = 1 + ( z − 1 ) G = 1 + M 1 − γ G ≥ 1 + γ M ( 1 − γ ) L ≥ 1 + γ 1 − γ = γ 1 . where the first inequality follows from the previous G ≥ L γ G \ge\frac{L}{\gamma} G ≥ γ L L ≥ M L \ge M L ≥ M
Subsequently, for any k ∈ { 1 − L , … , h − 1 } k \in\{1-L,\ldots,h-1\} k ∈ { 1 − L , … , h − 1 }
u k ≜ max { 0 , k } , v k ≜ min { h , k + L } , u_k \triangleq\max\{0,k\}, \qquad v_k \triangleq\min\{h,k+L\}, u k ≜ max { 0 , k } , v k ≜ min { h , k + L } , and assign each equation B k ≜ γ x v k − x u k + γ ∑ j = u k + 1 v k d i + j − 1 − ( v k − u k ) d i + u k B_k \triangleq\gamma x_{v_k}-x_{u_k}+\gamma\sum_{j=u_k+1}^{v_k}d_{i+j-1}-(v_k-u_k)d_{i+u_k} B k ≜ γ x v k − x u k + γ ∑ j = u k + 1 v k d i + j − 1 − ( v k − u k ) d i + u k w k ≜ z h − 1 − k G w_k \triangleq\frac{z^{h-1-k}}{G} w k ≜ G z h − 1 − k
∑ k = 1 − L h − 1 w k B k − ∑ j = 1 h ( γ z L − 1 ) w j x j ≤ 0 , (59) \sum_{k=1-L}^{h-1}w_kB_k-\sum_{j=1}^{h}(\gamma z^L-1)w_jx_j\le0, \tag*{(59)} k = 1 − L ∑ h − 1 w k B k − j = 1 ∑ h ( γ z L − 1 ) w j x j ≤ 0 , (59) where B k ≤ 0 B_k\le0 B k ≤ 0 (58) and γ z L ≥ 1 \gamma z^L\ge1 γ z L ≥ 1
Then, we compute the coefficients of x 0 , … , x h x_0,\ldots,x_h x 0 , … , x h (59) . For any 1 ≤ j < h 1\le j<h 1 ≤ j < h x j x_j x j B j − L B_{j-L} B j − L γ w j − L \gamma w_{j-L} γ w j − L B j B_j B j − w j -w_j − w j − ∑ j = 1 h ( γ z L − 1 ) w j x j -\sum_{j=1}^{h}(\gamma z^L-1)w_jx_j − ∑ j = 1 h ( γ z L − 1 ) w j x j − ( γ z L − 1 ) w j -(\gamma z^L-1)w_j − ( γ z L − 1 ) w j x j x_j x j
γ w j − L − w j − ( γ z L − 1 ) w j = γ z L w j − w j − ( γ z L − 1 ) w j = 0 , \gamma w_{j-L}-w_j-(\gamma z^L-1)w_j=\gamma z^Lw_j-w_j-(\gamma z^L-1)w_j=0, γ w j − L − w j − ( γ z L − 1 ) w j = γ z L w j − w j − ( γ z L − 1 ) w j = 0 , where the identity follows from w j − L = z L w j w_{j-L}=z^Lw_j w j − L = z L w j x 1 , … , x h − 1 x_1,\ldots,x_{h-1} x 1 , … , x h − 1
It remains to compute the coefficients of the two boundary marginals. The term x h x_h x h B k B_k B k γ w k \gamma w_k γ w k k ∈ { h − L , … , h − 1 } k\in\{h-L,\ldots,h-1\} k ∈ { h − L , … , h − 1 } x h x_h x h
γ ∑ k = h − L h − 1 w k = γ 1 G ∑ a = 0 L − 1 z a = γ . \gamma\sum_{k=h-L}^{h-1}w_k=\gamma\frac{1}{G}\sum_{a=0}^{L-1}z^a=\gamma. γ k = h − L ∑ h − 1 w k = γ G 1 a = 0 ∑ L − 1 z a = γ . Similarly, x 0 x_0 x 0 B k B_k B k − w k -w_k − w k k ∈ { 1 − L , … , 0 } k\in\{1-L,\ldots,0\} k ∈ { 1 − L , … , 0 } x 0 x_0 x 0
− ∑ k = 1 − L 0 w k = z h − 1 G ∑ k = 1 − L 0 z − k = − z h − 1 G ∑ a = 0 L − 1 z a = − z h − 1 . (60) -\sum_{k=1-L}^{0}w_k=\frac{z^{h-1}}{G}\sum_{k=1-L}^{0}z^{-k}=-\frac{z^{h-1}}{G}\sum_{a=0}^{L-1}z^a=-z^{h-1}. \tag*{(60)} − k = 1 − L ∑ 0 w k = G z h − 1 k = 1 − L ∑ 0 z − k = − G z h − 1 a = 0 ∑ L − 1 z a = − z h − 1 . (60) Next, we compute the coefficients of d i , … , d i + h − i d_i,\ldots,d_{i+h-i} d i , … , d i + h − i (59) . Fix any 2 ≤ j ≤ h 2\le j\le h 2 ≤ j ≤ h d i + j − i d_{i+j-i} d i + j − i γ ∑ j = u k + 1 v k d i + j − 1 \gamma\sum_{j=u_k+1}^{v_k}d_{i+j-1} γ ∑ j = u k + 1 v k d i + j − 1 B k B_k B k k ∈ { j − L , j − L + 1 , … , j − 1 } k\in\{j-L,j-L+1,\ldots,j-1\} k ∈ { j − L , j − L + 1 , … , j − 1 } γ ∑ k = j − L j − 1 w k = γ w j − 1 ∑ a = 0 L − 1 z a = γ w j − 1 G \gamma\sum_{k=j-L}^{j-1} w_k = \gamma w_{j-1}\sum_{a=0}^{L-1}z^a = \gamma w_{j-1}G γ ∑ k = j − L j − 1 w k = γ w j − 1 ∑ a = 0 L − 1 z a = γ w j − 1 G d i + j − i d_{i+j-i} d i + j − i B j − 1 B_{j-1} B j − 1 − ( v j − 1 − u j − 1 ) w j − 1 -(v_{j-1}-u_{j-1})w_{j-1} − ( v j − 1 − u j − 1 ) w j − 1 v j − 1 − u j − 1 ≤ L v_{j-1}-u_{j-1}\le L v j − 1 − u j − 1 ≤ L c j c_j c j d i + j − 1 d_{i+j-1} d i + j − 1
c j = γ w j − 1 G − ( v j − 1 − u j − 1 ) w j − 1 ≥ ( γ G − L ) w j − 1 ≥ 0 , 2 ≤ j ≤ h , c_j=\gamma w_{j-1}G-(v_{j-1}-u_{j-1})w_{j-1}\ge(\gamma G-L)w_{j-1}\ge0,\qquad2\le j\le h, c j = γ w j − 1 G − ( v j − 1 − u j − 1 ) w j − 1 ≥ ( γ G − L ) w j − 1 ≥ 0 , 2 ≤ j ≤ h , where the last inequality follows from γ G ≥ L \gamma G\ge L γ G ≥ L
It remains to compute the coefficient of d i d_i d i d i d_i d i γ ∑ j = u k + 1 v k d i + j − 1 \gamma\sum_{j=u_k+1}^{v_k}d_{i+j-1} γ ∑ j = u k + 1 v k d i + j − 1 B k B_k B k k ∈ { 1 − L , … , 0 } k\in\{1-L,\ldots,0\} k ∈ { 1 − L , … , 0 } γ ∑ k = 1 − L 0 w k \gamma\sum_{k=1-L}^{0}w_k γ ∑ k = 1 − L 0 w k − ∑ k = 1 − L 0 v k w k -\sum_{k=1-L}^{0}v_kw_k − ∑ k = 1 − L 0 v k w k C C C d i d_i d i
C = γ ∑ k = 1 − L 0 w k − ∑ k = 1 − L 0 v k w k ≥ ( γ − L ) ∑ k = 1 − L 0 w k = ( γ − L ) z h − 1 , C=\gamma\sum_{k=1-L}^{0}w_k-\sum_{k=1-L}^{0}v_kw_k\ge(\gamma-L)\sum_{k=1-L}^{0}w_k=(\gamma-L)z^{h-1}, C = γ k = 1 − L ∑ 0 w k − k = 1 − L ∑ 0 v k w k ≥ ( γ − L ) k = 1 − L ∑ 0 w k = ( γ − L ) z h − 1 , where the first inequality comes from v k ≤ L v_k\le L v k ≤ L (60) .
Combining the preceding coefficient calculations, we obtain
∑ k = 1 − L h − 1 w k B k − ∑ j = 1 h − 1 ( γ z L − 1 ) w j x j = γ x h − z h − 1 ⋅ x 0 + C ⋅ d i + ∑ j = 2 h − 1 c j d i + j − 1 ≤ 0. \sum_{k=1-L}^{h-1}w_kB_k-\sum_{j=1}^{h-1}(\gamma z^L-1)w_jx_j=\gamma x_h-z^{h-1}\cdot x_0+C\cdot d_i+\sum_{j=2}^{h-1}c_jd_{i+j-1}\le0. k = 1 − L ∑ h − 1 w k B k − j = 1 ∑ h − 1 ( γ z L − 1 ) w j x j = γ x h − z h − 1 ⋅ x 0 + C ⋅ d i + j = 2 ∑ h − 1 c j d i + j − 1 ≤ 0. Due to c j ≥ 0 c_j\ge0 c j ≥ 0
γ x h ≤ z h − 1 ⋅ x 0 − C ⋅ d i ≤ ( z h − 1 − C ) d i ≤ ( 1 − γ + L ) z h − 1 ⋅ d i . \gamma x_h\le z^{h-1}\cdot x_0-C\cdot d_i\le(z^{h-1}-C)d_i\le(1-\gamma+L)z^{h-1}\cdot d_i. γ x h ≤ z h − 1 ⋅ x 0 − C ⋅ d i ≤ ( z h − 1 − C ) d i ≤ ( 1 − γ + L ) z h − 1 ⋅ d i . Finally, z h − 1 = ( 1 + 1 − γ M ) h − 1 ≤ exp ( ( 1 − γ ) ( h − 1 ) M ) ≤ e z^{h-1}=\left(1+\frac{1-\gamma}{M}\right)^{h-1}\le\exp\left(\frac{(1-\gamma)(h-1)}{M}\right)\le e z h − 1 = ( 1 + M 1 − γ ) h − 1 ≤ exp ( M ( 1 − γ ) ( h − 1 ) ) ≤ e L = ⌈ 5 M ⌉ L=\lceil5M\rceil L = ⌈ 5 M ⌉ γ ≥ 1 / 2 \gamma\ge1/2 γ ≥ 1/2 M ≥ 3 M\ge3 M ≥ 3 1 − γ + L ≤ 3 2 + 5 M ≤ 11 2 M 1-\gamma+L\le\frac{3}{2}+5M\le\frac{11}{2}M 1 − γ + L ≤ 2 3 + 5 M ≤ 2 11 M γ x h ≤ ( 1 − γ + L ) z h − 1 ⋅ d i ≤ 11 2 M ⋅ d i ≤ 15 M ⋅ d i \gamma x_h\le(1-\gamma+L)z^{h-1}\cdot d_i\le\frac{11}{2}M\cdot d_i\le15M\cdot d_i γ x h ≤ ( 1 − γ + L ) z h − 1 ⋅ d i ≤ 2 11 M ⋅ d i ≤ 15 M ⋅ d i M = 3 + ( 1 − γ ) h M=3+(1-\gamma)h M = 3 + ( 1 − γ ) h h = t − i + 1 h=t-i+1 h = t − i + 1
γ f ( o i ∣ S t ) = γ x h ≤ 15 M ⋅ d i = 15 ( 3 + ( 1 − γ ) ( t − i + 1 ) ) d i . \gamma f(o_i\mid S_t)=\gamma x_h\le15M\cdot d_i=15(3+(1-\gamma)(t-i+1))d_i. γ f ( o i ∣ S t ) = γ x h ≤ 15 M ⋅ d i = 15 ( 3 + ( 1 − γ ) ( t − i + 1 )) d i . Proof of Theorem 4.10
Proof. The term γ / r \gamma/r γ / r Theorem 4.6 . We prove the second term. We set
H ≜ 15 ( 1 − γ ) , F ~ t ≜ H F t , K ~ t ≜ H K t , M ~ ≜ H F r . H\triangleq15(1-\gamma),\qquad\widetilde{F}_t\triangleq HF_t,\qquad\widetilde{K}_t\triangleq HK_t,\qquad\widetilde{M}\triangleq HF_r. H ≜ 15 ( 1 − γ ) , F t ≜ H F t , K t ≜ H K t , M ≜ H F r . Because 1 / 2 ≤ γ < 1 1/2\le\gamma<1 1/2 ≤ γ < 1 H > 0 H>0 H > 0 Lemma 4.9 implies, for every t < r t<r t < r
γ 2 OPT ≤ D γ F t + H K t + γ ( r − t ) ( F t + 1 − F t ) ≤ D γ H F ~ t + K ~ t + γ r H ( F ~ t + 1 − F ~ t ) . \gamma^2\operatorname{OPT}\le D_\gamma F_t+HK_t+\gamma(r-t)(F_{t+1}-F_t)\le\frac{D_\gamma}{H}\widetilde{F}_t+\widetilde{K}_t+\frac{\gamma r}{H}(\widetilde{F}_{t+1}-\widetilde{F}_t). γ 2 OPT ≤ D γ F t + H K t + γ ( r − t ) ( F t + 1 − F t ) ≤ H D γ F t + K t + H γ r ( F t + 1 − F t ) . Particularly when t = r t=r t = r γ 2 OPT ≤ D γ H M ~ + K ~ r \gamma^2\operatorname{OPT}\le\frac{D_\gamma}{H}\widetilde{M}+\widetilde{K}_r γ 2 OPT ≤ H D γ M + K r
Then, if we apply Lemma 4.5 with
A = γ r H , B = D γ H , C = γ 2 OPT , M = M ~ , A=\frac{\gamma r}{H},\qquad B=\frac{D_\gamma}{H},\qquad C=\gamma^2\operatorname{OPT},\qquad M=\widetilde{M}, A = H γ r , B = H D γ , C = γ 2 OPT , M = M , we can have
γ 2 OPT ≤ ( D γ H + γ r H ( 1 − 1 r ) ) M ~ = ( D γ + H γ ( r − 1 ) ) F r = ( D γ + 15 γ ( 1 − γ ) ( r − 1 ) ) F r . \gamma^2\operatorname{OPT}\le\left(\frac{D_\gamma}{H}+\sqrt{\frac{\gamma r}{H}\left(1-\frac{1}{r}\right)}\right)\widetilde{M}=(D_\gamma+\sqrt{H\gamma(r-1)})F_r=(D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)})F_r. γ 2 OPT ≤ ( H D γ + H γ r ( 1 − r 1 ) ) M = ( D γ + H γ ( r − 1 ) ) F r = ( D γ + 15 γ ( 1 − γ ) ( r − 1 ) ) F r . Therefore,
F r OPT ≥ γ 2 D γ + 15 γ ( 1 − γ ) ( r − 1 ) . \frac{F_r}{\operatorname{OPT}}\ge\frac{\gamma^2}{D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)}}. OPT F r ≥ D γ + 15 γ ( 1 − γ ) ( r − 1 ) γ 2 . Proof of Theorem 4.11
Proof. The first three terms in Eq. (36) come from Eq. (31) . We next prove the final term in Eq. (36) . If 0 < γ ≤ 1 / 2 0 < \gamma\le1/2 0 < γ ≤ 1/2 2 ( 1 − γ ) ≥ 1 2(1-\gamma) \ge1 2 ( 1 − γ ) ≥ 1
B γ + γ ( r − 1 ) ≤ B γ + 2 γ ( 1 − γ ) ( r − 1 ) ≤ 2 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . B_\gamma+ \sqrt{\gamma(r-1)} \le B_\gamma+ \sqrt{2\gamma(1-\gamma)(r-1)} \le\sqrt{2}\left(B_\gamma+ \sqrt{\gamma(1-\gamma)(r-1)}\right). B γ + γ ( r − 1 ) ≤ B γ + 2 γ ( 1 − γ ) ( r − 1 ) ≤ 2 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . Thus, we can show that, when 0 < γ ≤ 1 / 2 0 < \gamma\le1/2 0 < γ ≤ 1/2
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) } ≥ 1 2 γ 2 B γ + γ ( 1 − γ ) ( r − 1 ) ≥ γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . R_{\mathrm{gr}}(\gamma,r) \ge\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}}\right\} \ge\frac{1}{\sqrt{2}}\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}} \ge\frac{\gamma^2}{14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}. R gr ( γ , r ) ≥ max { r γ , B γ + γ ( r − 1 ) γ 2 } ≥ 2 1 B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 ≥ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 . where the first inequality follows from Eq. (29) .
It remains to consider 1 / 2 ≤ γ < 1 1/2 \le\gamma< 1 1/2 ≤ γ < 1 δ ≔ 1 − γ \delta\coloneqq1-\gamma δ : = 1 − γ
γ 2 B γ + γ ( r − 1 ) ≥ γ 2 1 − γ B γ + γ ( 1 − γ ) ( r − 1 ) . \frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}} \ge\frac{\gamma^2\sqrt{1-\gamma}}{B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}}. B γ + γ ( r − 1 ) γ 2 ≥ B γ + γ ( 1 − γ ) ( r − 1 ) γ 2 1 − γ . Thus, when 1 − γ ≥ 1 / 14 \sqrt{1-\gamma} \ge1/14 1 − γ ≥ 1/14
R g r ( γ , r ) ≥ max { γ r , γ 2 B γ + γ ( r − 1 ) } ≥ γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . R_{\mathrm{gr}}(\gamma,r) \ge\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{B_\gamma+\sqrt{\gamma(r-1)}}\right\} \ge\frac{\gamma^2}{14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}. R gr ( γ , r ) ≥ max { r γ , B γ + γ ( r − 1 ) γ 2 } ≥ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 . Now, we suppose that 1 − γ < 1 / 14 \sqrt{1-\gamma}<1/14 1 − γ < 1/14 Theorem 4.10 : when 1 / 2 ≤ γ < 1 1/2 \le\gamma< 1 1/2 ≤ γ < 1
R g r ( γ , r ) ≥ max { γ r , γ 2 D γ + 15 γ ( 1 − γ ) ( r − 1 ) } , R_{\mathrm{gr}}(\gamma,r) \ge\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)}}\right\}, R gr ( γ , r ) ≥ max { r γ , D γ + 15 γ ( 1 − γ ) ( r − 1 ) γ 2 } , where D γ ≔ 60 − 15 γ + γ 2 D_\gamma\coloneqq60-15\gamma+\gamma^2 D γ : = 60 − 15 γ + γ 2 D γ + 15 γ ( 1 − γ ) ( r − 1 ) D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)} D γ + 15 γ ( 1 − γ ) ( r − 1 ) 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) 14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right) 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) )
D γ + 15 γ ( 1 − γ ) ( r − 1 ) − 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) = 18 + 27 ( 1 − γ ) − 13 ( 1 − γ ) 2 − ( 14 − 15 ) γ ( 1 − γ ) ( r − 1 ) . \begin{aligned}
&D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)}-14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)\\
&=18+27(1-\gamma)-13(1-\gamma)^2-(14-\sqrt{15})\sqrt{\gamma(1-\gamma)(r-1)}.
\end{aligned} D γ + 15 γ ( 1 − γ ) ( r − 1 ) − 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) = 18 + 27 ( 1 − γ ) − 13 ( 1 − γ ) 2 − ( 14 − 15 ) γ ( 1 − γ ) ( r − 1 ) . If setting u ≔ γ ( 1 − γ ) ( r − 1 ) u\coloneqq\sqrt{\gamma(1-\gamma)(r-1)} u : = γ ( 1 − γ ) ( r − 1 ) u ≥ 9 / 5 u\ge9/5 u ≥ 9/5
18 + 27 ( 1 − γ ) − 13 ( 1 − γ ) 2 < 18 + 27 ( 1 − γ ) < 18 + 27 196 < ( 14 − 15 ) 9 5 ≤ ( 14 − 15 ) u , 18+27(1-\gamma)-13(1-\gamma)^2 < 18+27(1-\gamma) < 18+\frac{27}{196} < (14-\sqrt{15})\frac{9}{5} \le(14-\sqrt{15})u, 18 + 27 ( 1 − γ ) − 13 ( 1 − γ ) 2 < 18 + 27 ( 1 − γ ) < 18 + 196 27 < ( 14 − 15 ) 5 9 ≤ ( 14 − 15 ) u , where the second inequality follows from 1 − γ < 1 / 14 \sqrt{1-\gamma}<1/14 1 − γ < 1/14 15 < 31 / 8 \sqrt{15}<31/8 15 < 31/8 ( 14 − 31 / 8 ) ( 9 / 5 ) = 729 / 40 = 18 + 9 40 ≥ 18 + 27 196 (14-31/8)(9/5)=729/40=18+\frac{9}{40}\ge18+\frac{27}{196} ( 14 − 31/8 ) ( 9/5 ) = 729/40 = 18 + 40 9 ≥ 18 + 196 27
D γ + 15 γ ( 1 − γ ) ( r − 1 ) ≤ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)}\le14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right) D γ + 15 γ ( 1 − γ ) ( r − 1 ) ≤ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) such that
R g r ( γ , r ) ≥ max { γ r , γ 2 D γ + 15 γ ( 1 − γ ) ( r − 1 ) } ≥ γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . R_{\mathrm{gr}}(\gamma,r)\ge\max\left\{\frac{\gamma}{r},\frac{\gamma^2}{D_\gamma+\sqrt{15\gamma(1-\gamma)(r-1)}}\right\}\ge\frac{\gamma^2}{14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}. R gr ( γ , r ) ≥ max { r γ , D γ + 15 γ ( 1 − γ ) ( r − 1 ) γ 2 } ≥ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 . Finally, we suppose that u < 9 / 5 u < 9/5 u < 9/5 x ≜ γ r + 1 x \triangleq\gamma^{r+1} x ≜ γ r + 1
γ r + 1 2 − γ + γ r + 1 / γ 2 B γ + u = γ r + 1 ( B γ + u ) γ 2 ( 2 − γ + γ r + 1 ) = x ( B γ + u ) γ 2 ( 2 − γ + x ) . \frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}} \bigg/ \frac{\gamma^2}{B_\gamma+u} = \frac{\gamma^{r+1}(B_\gamma+u)}{\gamma^2(2-\gamma+\gamma^{r+1})} = \frac{x(B_\gamma+u)}{\gamma^2(2-\gamma+x)}. 2 − γ + γ r + 1 γ r + 1 / B γ + u γ 2 = γ 2 ( 2 − γ + γ r + 1 ) γ r + 1 ( B γ + u ) = γ 2 ( 2 − γ + x ) x ( B γ + u ) . Moreover, 1 − γ < 1 / 14 \sqrt{1-\gamma}<1/14 1 − γ < 1/14 γ > 195 / 196 \gamma>195/196 γ > 195/196
B γ ≜ 2 − γ + γ 2 ≥ b 0 ≜ 2 − 1 196 + 1 196 2 , 2 − γ ≤ c 0 ≜ 197 196 . B_\gamma\triangleq2-\gamma+\gamma^2 \ge b_0 \triangleq2-\frac{1}{196}+\frac{1}{196^2}, \qquad2-\gamma\le c_0 \triangleq\frac{197}{196}. B γ ≜ 2 − γ + γ 2 ≥ b 0 ≜ 2 − 196 1 + 19 6 2 1 , 2 − γ ≤ c 0 ≜ 196 197 . Therefore, we can get
γ r + 1 2 − γ + γ r + 1 / γ 2 B γ + u = x ( B γ + u ) γ 2 ( 2 − γ + x ) ≥ x ( B γ + u ) 2 − γ + x ≥ x ( b 0 + u ) c 0 + x . (61) \frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}} \bigg/ \frac{\gamma^2}{B_\gamma+u} = \frac{x(B_\gamma+u)}{\gamma^2(2-\gamma+x)} \ge\frac{x(B_\gamma+u)}{2-\gamma+x} \ge\frac{x(b_0+u)}{c_0+x}. \tag*{(61)} 2 − γ + γ r + 1 γ r + 1 / B γ + u γ 2 = γ 2 ( 2 − γ + x ) x ( B γ + u ) ≥ 2 − γ + x x ( B γ + u ) ≥ c 0 + x x ( b 0 + u ) . (61) The inequality log γ ≥ − ( 1 − γ ) / γ \log\gamma\ge-(1-\gamma)/\gamma log γ ≥ − ( 1 − γ ) / γ
− log x = − ( r + 1 ) log γ ≤ ( 1 − γ ) ( r + 1 ) γ = γ ( 1 − γ ) ( r − 1 ) γ 2 + 2 ( 1 − γ ) γ = u 2 γ 2 + 2 ( 1 − γ ) γ . (62) -\log x=-(r+1)\log\gamma\le\frac{(1-\gamma)(r+1)}{\gamma}=\frac{\gamma(1-\gamma)(r-1)}{\gamma^2}+\frac{2(1-\gamma)}{\gamma}=\frac{u^2}{\gamma^2}+\frac{2(1-\gamma)}{\gamma}. \tag*{(62)} − log x = − ( r + 1 ) log γ ≤ γ ( 1 − γ ) ( r + 1 ) = γ 2 γ ( 1 − γ ) ( r − 1 ) + γ 2 ( 1 − γ ) = γ 2 u 2 + γ 2 ( 1 − γ ) . (62) Since u < 9 / 5 u<9/5 u < 9/5 (62) yields − log x < 81 25 ( 196 195 ) 2 + 2 195 < log 27 -\log x<\frac{81}{25}\left(\frac{196}{195}\right)^2+\frac{2}{195}<\log27 − log x < 25 81 ( 195 196 ) 2 + 195 2 < log 27 x > 1 / 27 x>1/27 x > 1/27 x / ( c 0 + x ) x/(c_0+x) x / ( c 0 + x ) x x x
γ r + 1 2 − γ + γ r + 1 / γ 2 B γ + u ≥ x ( b 0 + u ) c 0 + x > b 0 + u 27 c 0 + 1 . \frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}} \bigg/ \frac{\gamma^2}{B_\gamma+u} \ge\frac{x(b_0+u)}{c_0+x} > \frac{b_0+u}{27c_0+1}. 2 − γ + γ r + 1 γ r + 1 / B γ + u γ 2 ≥ c 0 + x x ( b 0 + u ) > 27 c 0 + 1 b 0 + u . If u ≥ 1 / 64 u\ge1/64 u ≥ 1/64
b 0 + u 27 c 0 + 1 ≥ b 0 + 1 / 64 27 c 0 + 1 = 1 14 + 109 4323760 > 1 14 \frac{b_0+u}{27c_0+1}\ge\frac{b_0+1/64}{27c_0+1}=\frac{1}{14}+\frac{109}{4323760}>\frac{1}{14} 27 c 0 + 1 b 0 + u ≥ 27 c 0 + 1 b 0 + 1/64 = 14 1 + 4323760 109 > 14 1 such that
R g r ( γ , r ) ≥ γ r + 1 2 − γ + γ r + 1 ≥ γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . R_{\rm gr}(\gamma,r)\ge\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}\ge\frac{\gamma^2}{14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}. R gr ( γ , r ) ≥ 2 − γ + γ r + 1 γ r + 1 ≥ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 . If u < 1 / 64 u<1/64 u < 1/64 (62) gives − log x < 1 4096 ( 196 195 ) 2 + 2 195 < log 2 -\log x<\frac{1}{4096}\left(\frac{196}{195}\right)^2+\frac{2}{195}<\log2 − log x < 4096 1 ( 195 196 ) 2 + 195 2 < log 2 x > 1 / 2 x>1/2 x > 1/2
x ( b 0 + u ) c 0 + x > b 0 2 c 0 + 1 ≈ 0.662721 > 1 14 , \frac{x(b_0+u)}{c_0+x}>\frac{b_0}{2c_0+1}\approx0.662721>\frac{1}{14}, c 0 + x x ( b 0 + u ) > 2 c 0 + 1 b 0 ≈ 0.662721 > 14 1 , which indicates that
R g r ( γ , r ) ≥ γ r + 1 2 − γ + γ r + 1 ≥ γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) . R_{\rm gr}(\gamma,r)\ge\frac{\gamma^{r+1}}{2-\gamma+\gamma^{r+1}}\ge\frac{\gamma^2}{14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}. R gr ( γ , r ) ≥ 2 − γ + γ r + 1 γ r + 1 ≥ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 . As a result, for every 0 < γ ≤ 1 0<\gamma\le1 0 < γ ≤ 1 r ≥ 2 r\ge2 r ≥ 2
R g r ( γ , r ) ≥ γ 2 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) , R_{\rm gr}(\gamma,r)\ge\frac{\gamma^2}{14\left(B_\gamma+\sqrt{\gamma(1-\gamma)(r-1)}\right)}, R gr ( γ , r ) ≥ 14 ( B γ + γ ( 1 − γ ) ( r − 1 ) ) γ 2 , which proves Eq. (36) in Theorem 4.11.
