Introduction
Real-life optimization problems usually have to deal with uncertainty, such as delays, unpredictable demand, or weather. There is a wide body of literature modeling uncertainty for various kinds of optimization problems. Notably, stochastic models have enjoyed widespread study and use, but they require some information about the probabilities of some possibly extreme events, which is difficult to estimate or model. A somewhat opposite view on the guarantees that we seek is the worst-case model, in which we are interested in ensuring some optimization guarantee on any possible scenario, irrespective of their likeliness.
Consider for example a mailperson who wants to deliver letters to n n n A A A B B B [ ℓ A B , u A B ] [\ell_{AB},u_{AB}] [ ℓ A B , u A B ]
Now that we have two vectors, ℓ \ell ℓ u u u [6 ] have introduced an approximation framework which ensures that the solution is comparatively close to the optimum on each scenario. For a solution S S S r S r_S r S w ∈ [ ℓ , u ] w \in[\ell,u] w ∈ [ ℓ , u ] w ( S ) − opt w w(S)-\operatorname{opt}_w w ( S ) − opt w w ( S ) : = ∑ e ∈ S w e w(S):=\sum_{e\in S}w_e w ( S ) := ∑ e ∈ S w e opt w \operatorname{opt}_w opt w w w w
We can now introduce a measure of how uncertain the problem is by letting M R = min solution S r S \mathrm{MR}=\min_{\text{solution }S}r_S MR = min solution S r S
For some α , β ≥ 1 \alpha,\beta\ge1 α , β ≥ 1 S S S ( α , β ) (\alpha,\beta) ( α , β ) w ∈ [ ℓ , u ] w\in[\ell,u] w ∈ [ ℓ , u ] w ( S ) ≤ α ⋅ opt w + β ⋅ M R w(S)\le\alpha\cdot\operatorname{opt}_w+\beta\cdot\mathrm{MR} w ( S ) ≤ α ⋅ opt w + β ⋅ MR opt w \operatorname{opt}_w opt w β = 0 \beta=0 β = 0 α = 0 \alpha=0 α = 0 ℓ = u \ell=u ℓ = u = 0 =0 = 0 ℓ = u \ell=u ℓ = u ( 1 , 1 ) (1,1) ( 1 , 1 )
Our contributions. In this article, we make three significant contributions.
In Section 3, we show how to convert any difference-approximation algorithm for a linear selection problem (both notions are defined formally below) to a robust approximation algorithm in the case where the lower bound on the weights is ℓ = 0 \ell=0 ℓ = 0
Theorem 4. Any linear selection problem P \mathcal{P} P polynomial-time γ \gamma γ difference approximation algorithm and a λ \lambda λ approximation algorithm also admits a polynomial-time ( λ δ , λ ( δ γ + 1 ) ) (\lambda\delta,\lambda(\delta\gamma+1)) ( λ δ , λ ( δ γ + 1 )) robust approximation algorithm in the ℓ = 0 \ell=0 ℓ = 0 δ \delta δ P \mathcal{P} P
In the general ℓ \ell ℓ [6 ] by abstracting away the specificities of the local search algorithm.
This will allow us to conclude with the first robust approximation for Weighted k k k H k H_k H k k k k
Theorem 22. The Weighted k k k admits a ( O ( H k 2 ) , O ( H k 3 k ) ) (O(H_k^2),O(H_k^3 k)) ( O ( H k 2 ) , O ( H k 3 k ))
The Weighted k k k Ω \Omega Ω k k k w : Ω → R + w:\Omega\to\mathbb{R}^{+} w : Ω → R + S ⊆ Ω S \subseteq\Omega S ⊆ Ω ⋃ Ω \bigcup\Omega ⋃ Ω w ( S ) = ∑ s ∈ S w ( s ) w(S)=\sum_{s\in S}w(s) w ( S ) = ∑ s ∈ S w ( s ) ln k − O ( ln ln k ) \ln k-O(\ln\ln k) ln k − O ( ln ln k ) [7 ] .
We believe that this new formalization of properties of local search algorithms that lead to a robust approximation algorithm could lead to new avenues of research in local search-based approximation algorithms. Furthermore, this is the first robust approximation algorithm for an NP-hard problem since Ganesh, Maggs and Panigrahi published their robust approximations for TSP and Steiner Tree in 2020.
Structure of the paper. After a brief overview of related work and an introduction of the definitions in Section 2, we start, in Section 3, with a restricted case in which the lower bound weight vector ℓ \ell ℓ 0 0 0 ℓ ≠ 0 \ell\ne0 ℓ = 0 k k k
Related Work There is a large body of work on stochastic optimization [11 ] , in which some data about the distribution of the constraints is known, but as mentioned in [10 ] , this data may not be available, and furthermore, having expected or probable guarantees may not be sufficient if we want to design solutions that work as well as possible no matter the scenario.
Research on optimization under worst-case uncertainty constraints dates back to at least the short paper by Soyster [13 ] , in which he shows how to convert a linear program (LP) with inexact constraints into an exact auxiliary linear program. The approaches of [5 ] and [12 ] solve the problem in a similar fashion. In [3 ] , Ben-Tal and Nemirovski follow a similar idea but allow for ellipsoidal uncertainty, and therefore, the exact auxiliary program they use is a conic quadratic program instead of simply a linear one. Another approach is that from [4 ] , in which there is a parameter quantifying how many coefficients of the constraint matrix can change inside of their respective uncertainty interval. In each of these papers, it is possible to cast the uncertain linear program into some other program that is also solvable in polynomial time.
In general, it is not possible to transform a program with uncertainty into another program which may be more complex, but that can be solved exactly using standard techniques, and therefore, the idea of min-max regret optimization has surveyed in [1 ] as another approach in which we measure a solution’s performance by its difference in weight with the optimal solution on every scenario, and try to minimize the largest difference. In [8 ] , Kasperski provides, to the best of our knowledge, the first approximation results for interval uncertainty, by showing how to compute a solution that has a regret that is bounded in terms of the minimal regret a solution can obtain. In a long series of articles summarized in [9 ] , several complexity results and more approximation algorithms have been found for various well-known problems. In particular, while [2 ] showed that the Robust Minimal Spanning Tree Problem is NP-hard, it admits a ( 1 , 2 ) (1,2) ( 1 , 2 ) [8 ] . The technique is general and very elegant, as it simply consists in computing the optimal solution on the midpoint scenario (that is, ℓ + u 2 \frac{\ell+u}{2} 2 ℓ + u
Our work mainly builds on the paper by Ganesh, Maggs and Panigrahi [6 ] , which provides the first approximation results for NP-hard problems (Traveling Salesperson and Steiner Tree) in the min-max regret setting.
Robust linear optimization problems
In this article, we consider linear selection problems , which we define as problems that can be modeled as 0-1 integer programs (IP) of the form
min w T x A x ≤ b x ∈ { 0 , 1 } n , \begin{aligned}
\min\quad& w^{T}x \\
& Ax \le b \\
& x \in\{0,1\}^{n},
\end{aligned} min w T x A x ≤ b x ∈ { 0 , 1 } n , where A A A b b b w w w P = ( n , Ω , A , b ) \mathcal{P}=(n,\Omega,A,b) P = ( n , Ω , A , b ) Ω \Omega Ω n n n x i x_i x i i i i Ω \Omega Ω S S S P \mathcal{P} P x x x x x x S S S A x ≤ b Ax \le b A x ≤ b A x ≤ b Ax \le b A x ≤ b
In order to study the robust variant of this problem, we use a robust formulation of P \mathcal{P} P robust linear optimization problem P R \mathcal{P}_{R} P R P \mathcal{P} P ℓ , u ∈ R n \ell,u \in\mathbb{R}^{n} ℓ , u ∈ R n ℓ i ≤ u i \ell_i \le u_i ℓ i ≤ u i i ∈ Ω i \in\Omega i ∈ Ω
argmin x ∈ { 0 , 1 } n max w ∈ [ ℓ , u ] ( w T x − opt w ) \underset{x \in\{0,1\}^{n}}{\operatorname{argmin}}\ \underset{w \in[\ell,u]}{\max}\ (w^{T}x-\operatorname{opt}_{w}) x ∈ { 0 , 1 } n argmin w ∈ [ ℓ , u ] max ( w T x − opt w ) (we denote [ ℓ , u ] = { w ∈ R n ∣ ∀ i ∈ Ω , w i ∈ [ ℓ i , u i ] } [\ell,u]=\{w\in\mathbb{R}^{n}\mid\forall i\in\Omega,w_i\in[\ell_i,u_i]\} [ ℓ , u ] = { w ∈ R n ∣ ∀ i ∈ Ω , w i ∈ [ ℓ i , u i ]} opt w \operatorname{opt}_{w} opt w P \mathcal{P} P w w w
Our goal is to transform an approximation algorithm for problem P \mathcal{P} P P R \mathcal{P}_{R} P R A \mathcal{A} A ( α , β ) (\alpha,\beta) ( α , β ) P R \mathcal{P}_{R} P R ( ℓ , u ) (\ell,u) ( ℓ , u ) sol \operatorname{sol} sol A \mathcal{A} A ∀ w ∈ [ ℓ , u ] , w ( sol ) ≤ α ⋅ opt w + β ⋅ M R \forall w\in[\ell,u],w(\operatorname{sol})\le\alpha\cdot\operatorname{opt}_{w}+\beta\cdot\mathrm{MR} ∀ w ∈ [ ℓ , u ] , w ( sol ) ≤ α ⋅ opt w + β ⋅ MR M R \mathrm{MR} MR P R \mathcal{P}_{R} P R
The core result of [6 ] is to show that one way to get a robust algorithm is to find an approximate separation oracle for the linear programming (LP) relaxation of P R \mathcal{P}_{R} P R
min r ∀ w ∈ [ ℓ , u ] , w T x ≤ opt w + r (regret constraints) A x ≤ b (problem constraints) r ≥ 0 x ∈ [ 0 , 1 ] n . \begin{aligned}
\min\quad&r\\
\forall w\in[\ell,u],\quad&w^{T}x\le\operatorname{opt}_{w}+r &&\text{(regret constraints)}\\
&Ax\le b &&\text{(problem constraints)}\\
&r\ge0\\
&x\in[0,1]^{n}.
\end{aligned} min ∀ w ∈ [ ℓ , u ] , r w T x ≤ opt w + r A x ≤ b r ≥ 0 x ∈ [ 0 , 1 ] n . (regret constraints) (problem constraints) Indeed, a usual separation oracle would not be enough here, because there is an infinite number of constraints (which could be reduced to exponential by looking only at weight functions that take extremal values on every element) that each involve an NP-hard optimum. Therefore, we look at the following relaxed definition:
Definition 1 (Approximate Separation Oracle). A polynomial-time algorithm S \mathcal{S} S ( α , β ) (\alpha,\beta) ( α , β ) P R \mathcal{P}_{R} P R ( x , r ) (x,r) ( x , r )
returns some constraint of the LP formulation that is unsatisfied by ( x , r ) (x,r) ( x , r )
returns Feasible, in which case x x x P \mathcal{P} P P R \mathcal{P}_{R} P R
∀ w ∈ [ ℓ , u ] , w T x ≤ α ⋅ opt w + β ⋅ r . \forall w\in[\ell,u],\ w^{T}x\le\alpha\cdot\operatorname{opt}_{w}+\beta\cdot r. ∀ w ∈ [ ℓ , u ] , w T x ≤ α ⋅ opt w + β ⋅ r . With such an ASO, we can use Theorem 2.1 of [6 ] to get a robust approximation algorithm:
Theorem 2 (Theorem 2.1 of [6 ] ). If:
there is a polynomial-time γ \gamma γ P \mathcal{P} P
the integrality gap of the LP formulation of P \mathcal{P} P δ \delta δ
there is a ( α , β ) (\alpha,\beta) ( α , β ) P R \mathcal{P}_{R} P R
then there exists a polynomial-time ( γ δ , γ δ β + γ ) (\gamma\delta,\gamma\delta\beta+\gamma) ( γ δ , γ δ β + γ ) P R \mathcal{P}_{R} P R
In the context of regret minimization, a natural notion introduced by [6 ] is that of difference approximation , a notion defined on the original problem P \mathcal{P} P P R \mathcal{P}_{R} P R S S S O P T \mathrm{OPT} OPT S ∩ O P T S \cap\mathrm{OPT} S ∩ OPT w ∈ [ ℓ , u ] w \in[\ell,u] w ∈ [ ℓ , u ] w ( S ) − opt w = w ( S ∖ O P T w ) − w ( O P T w ∖ S ) w(S)-\operatorname{opt}_{w}=w(S\setminus\mathrm{OPT}_{w})-w(\mathrm{OPT}_{w}\setminus S) w ( S ) − opt w = w ( S ∖ OPT w ) − w ( OPT w ∖ S )
Definition 3 (Difference approximation). We say that a solution S S S γ \gamma γ
w ( S ∖ O P T w ) ≤ γ w ( O P T w ∖ S ) . w(S\setminus\mathrm{OPT}_{w})\leq\gamma w(\mathrm{OPT}_{w}\setminus S). w ( S ∖ OPT w ) ≤ γ w ( OPT w ∖ S ) . Finally, we will also say that, given two values x , y ≥ 0 x,y\geq0 x , y ≥ 0 ε > 0 \varepsilon>0 ε > 0 x x x ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) y y y x ∈ [ y , ( 1 + ε ) y ] x\in[y,(1+\varepsilon)y] x ∈ [ y , ( 1 + ε ) y ]
Now that the setting and some important definitions have been introduced, we can start with the special case where ℓ = 0 \ell=0 ℓ = 0
A difference approximation gives a robust approximation in the ℓ = 0 \ell=0 ℓ = 0
In this section, we show the following theorem:
Theorem 4. Any linear selection problem P \mathcal{P} P γ \gamma γ λ \lambda λ ( λ δ , λ ( δ γ + 1 ) ) (\lambda\delta,\lambda(\delta\gamma+1)) ( λ δ , λ ( δ γ + 1 )) ℓ = 0 \ell=0 ℓ = 0 δ \delta δ P \mathcal{P} P
In order to apply Theorem 2 , we will show how to get an ASO for the ℓ = 0 \ell=0 ℓ = 0 u u u P \mathcal{P} P γ \gamma γ A \mathcal{A} A γ ≥ 1 \gamma\geq1 γ ≥ 1
Check the problem constraints A x ≤ b Ax\leq b A x ≤ b
w ← w\leftarrow w ← ∀ i ∈ Ω \forall i\in\Omega ∀ i ∈ Ω w i = u i x i w_i=u_i x_i w i = u i x i
S ← S\leftarrow S ← A \mathcal{A} A w w w
if ∑ i ∉ S u i x i > r \sum_{i\notin S}u_i x_i>r ∑ i ∈ / S u i x i > r
return ∑ i ∉ S u i x i ≤ r \sum_{i\notin S}u_i x_i\leq r ∑ i ∈ / S u i x i ≤ r
else
return Feasible
Data: ( x , r ) (x,r) ( x , r ) P R \mathcal{P}_{R} P R
Algorithm 1: P R \mathcal{P}_{R} P R ( x , r ) (x,r) ( x , r ) ( 1 , γ ) (1,\gamma) ( 1 , γ ) P R \mathcal{P}_{R} P R
Lemma 5. Suppose that problem P \mathcal{P} P γ \gamma γ A \mathcal{A} A P R \mathcal{P}_{R} P R ℓ = 0 \ell=0 ℓ = 0 u u u P R \mathcal{P}_{R} P R ( 1 , γ ) (1,\gamma) ( 1 , γ ) P R \mathcal{P}_{R} P R
Proof. If there is a violation of a problem constraint, this is directly detected by Line 1 of Algorithm 1. If no violation is found, let S S S w w w i ∈ Ω i\in\Omega i ∈ Ω w i = u i x i w_i=u_i x_i w i = u i x i
The only other constraint violation that the algorithm can output is ∑ i ∉ S ′ u i x i ≤ r \sum_{i\notin S'}u_i x_i\leq r ∑ i ∈ / S ′ u i x i ≤ r w ′ w' w ′ S ′ S' S ′ ∑ i ∈ Ω w i ′ x i > w ′ ( S ′ ) + γ r \sum_{i\in\Omega}w'_i x_i>w'(S')+\gamma r ∑ i ∈ Ω w i ′ x i > w ′ ( S ′ ) + γ r ∑ i ∉ S u i x i > r \sum_{i\notin S}u_i x_i>r ∑ i ∈ / S u i x i > r w ′ , S ′ w',S' w ′ , S ′
We define w ∗ w^{*} w ∗
w i ∗ = { u i if i ∉ S ′ 0 otherwise for all i ∈ Ω . w_i^{*}=
\begin{cases}
u_i & \text{if }i\notin S'\\
0 & \text{otherwise}
\end{cases}
\qquad\text{for all }i\in\Omega. w i ∗ = { u i 0 if i ∈ / S ′ otherwise for all i ∈ Ω. Then:
w ( Ω ∖ S ′ ) = ∑ i ∈ Ω w i ∗ x i − w ( S ′ ) ≥ ∑ i ∈ Ω w i ′ x i − w ′ ( S ′ ) > γ r . w(\Omega\setminus S')=\sum_{i\in\Omega}w_i^{*}x_i-w(S')\geq\sum_{i\in\Omega}w'_i x_i-w'(S')>\gamma r. w ( Ω ∖ S ′ ) = i ∈ Ω ∑ w i ∗ x i − w ( S ′ ) ≥ i ∈ Ω ∑ w i ′ x i − w ′ ( S ′ ) > γ r . Now, remark that w ( Ω ∖ O P T w ) ≥ w ( Ω ∖ S ′ ) > γ r w(\Omega\setminus\mathrm{OPT}_w) \ge w(\Omega\setminus S') > \gamma r w ( Ω ∖ OPT w ) ≥ w ( Ω ∖ S ′ ) > γ r w ( Ω ∖ O P T w ) w(\Omega\setminus\mathrm{OPT}_w) w ( Ω ∖ OPT w ) w ( Ω ∖ S ) w(\Omega\setminus S) w ( Ω ∖ S ) S S S γ \gamma γ
w ( Ω ∖ S ) = w ( Ω ∖ ( S ∪ O P T w ) ) + w ( O P T w ∖ S ) ≥ w ( Ω ∖ ( S ∪ O P T w ) ) + 1 γ w ( S ∖ O P T w ) ( γ -difference approximation ) ≥ w ( Ω ∖ ( S ∪ O P T w ) ) + w ( S ∖ O P T w ) γ ≥ 1 γ w ( Ω ∖ O P T w ) > r . \begin{aligned}
w(\Omega\setminus S) &= w(\Omega\setminus(S \cup\mathrm{OPT}_w)) + w(\mathrm{OPT}_w \setminus S) \\
&\ge w(\Omega\setminus(S \cup\mathrm{OPT}_w)) + \frac{1}{\gamma}w(S \setminus\mathrm{OPT}_w) \quad(\gamma\text{-difference approximation}) \\
&\ge\frac{w(\Omega\setminus(S \cup\mathrm{OPT}_w)) + w(S \setminus\mathrm{OPT}_w)}{\gamma} \ge\frac{1}{\gamma}w(\Omega\setminus\mathrm{OPT}_w) > r.
\end{aligned} w ( Ω ∖ S ) = w ( Ω ∖ ( S ∪ OPT w )) + w ( OPT w ∖ S ) ≥ w ( Ω ∖ ( S ∪ OPT w )) + γ 1 w ( S ∖ OPT w ) ( γ -difference approximation ) ≥ γ w ( Ω ∖ ( S ∪ OPT w )) + w ( S ∖ OPT w ) ≥ γ 1 w ( Ω ∖ OPT w ) > r . Since Lemma 5 gives an ASO, using Theorem 2 directly implies Theorem 4. This result is a simple example of how to use Theorem 2 and ASOs in order to get robust approximation algorithms in the natural ℓ = 0 \ell= 0 ℓ = 0
The =0 case
In this section, we will provide a way to transform a local search approximation algorithm for some problem P \mathcal{P} P P \mathcal{P} P [6 ] , but they have been generalized in a way that allows their use on any local search algorithm satisfying three conditions, that will be specified in the next subsection, which will lead to the first robust approximation algorithm for Weighted k k k
We will assume that there is a local search approximation algorithm L \mathcal{L} L P \mathcal{P} P L \mathcal{L} L Φ \Phi Φ w w w i ∈ Ω i \in\Omega i ∈ Ω ϕ ( i ) \phi(i) ϕ ( i ) S ⊆ Ω S \subseteq\Omega S ⊆ Ω Φ ( S ) = ∑ i ∈ S ϕ ( i ) \Phi(S) = \sum_{i \in S}\phi(i) Φ ( S ) = ∑ i ∈ S ϕ ( i ) w = Φ w = \Phi w = Φ L \mathcal{L} L oblivious .
Starting from some solution S ⊆ Ω S \subseteq\Omega S ⊆ Ω Π S ⊆ 2 Ω \Pi_S \subseteq2^\Omega Π S ⊆ 2 Ω S S S S ′ ∈ Π S S' \in\Pi_S S ′ ∈ Π S L \mathcal{L} L L \mathcal{L} L γ \gamma γ S S S Φ \Phi Φ S ′ ∈ Π S S' \in\Pi_S S ′ ∈ Π S Φ ( S ) − Φ ( S ′ ) ≤ ϵ \Phi(S) - \Phi(S') \le\epsilon Φ ( S ) − Φ ( S ′ ) ≤ ϵ γ \gamma γ w w w
Prerequisites
We start by specifying formally the three properties Property 6, Property 9 and Property 12 that will be sufficient to get a robust approximation, together with some of their implications.
The well-behaved potential property asks that the potential can be decomposed as a sum over the elements of Ω \Omega Ω ℓ ≠ 0 \ell\ne0 ℓ = 0
The minimal move covering property provides a weight function α \alpha α 0 0 0 1 1 1
Finally, the efficient good move retrieval property ensures that a “good” enough move can be found in polynomial time, thereby allowing an algorithm to use the result of Lemma 11.
Well-Behaved Potential
The potential function we use to guide the local search toward a local minimum is a function of the weights of the elements of Ω \Omega Ω
Property 6 (Well-behaved potential). The potential function Φ ≥ 0 \Phi\ge0 Φ ≥ 0
There exists a function ϕ \phi ϕ Ω \Omega Ω Φ ( S ) = ∑ i ∈ S ϕ ( i ) \Phi(S) = \sum_{i \in S} \phi(i) Φ ( S ) = ∑ i ∈ S ϕ ( i ) S ⊆ Ω S \subseteq\Omega S ⊆ Ω
There exist two constants Λ 1 , Λ 2 > 0 \Lambda_1,\Lambda_2 > 0 Λ 1 , Λ 2 > 0 Λ 1 w ≤ Φ ≤ Λ 2 w \Lambda_1w \le\Phi\le\Lambda_2w Λ 1 w ≤ Φ ≤ Λ 2 w
Since we will manipulate two potential functions Φ \Phi Φ Φ ′ \Phi' Φ ′ ϕ , ϕ ′ \phi,\phi' ϕ , ϕ ′ Ω \Omega Ω Φ ( S ) = ∑ i ∈ S ϕ ( i ) \Phi(S) = \sum_{i \in S} \phi(i) Φ ( S ) = ∑ i ∈ S ϕ ( i ) Φ ′ ( S ) = ∑ i ∈ S ϕ ′ ( i ) \Phi'(S) = \sum_{i \in S} \phi'(i) Φ ′ ( S ) = ∑ i ∈ S ϕ ′ ( i ) Λ = Λ 2 / Λ 1 ≥ 1 \Lambda= \Lambda_2/\Lambda_1 \ge1 Λ = Λ 2 / Λ 1 ≥ 1
The first item of this property implies the following lemma, proven in [6 ] :
Lemma 7 (Lemma 5.12 from [6 ] ). Let A , B , C A,B,C A , B , C
Φ ( A ) − Φ ( B ) = [ Φ ( A ∖ C ) − Φ ( C ∖ A ) ] − [ Φ ( B ∖ C ) − Φ ( C ∖ B ) ] . \Phi(A) - \Phi(B) = [\Phi(A \setminus C) - \Phi(C \setminus A)] - [\Phi(B \setminus C) - \Phi(C \setminus B)]. Φ ( A ) − Φ ( B ) = [ Φ ( A ∖ C ) − Φ ( C ∖ A )] − [ Φ ( B ∖ C ) − Φ ( C ∖ B )] . We can also use the well-behaved potential property to show the following lemma:
Lemma 8. Fix any γ ≥ 1 \gamma\ge1 γ ≥ 1 L \mathcal{L} L γ \gamma γ γ \gamma γ
Proof. Let w w w Ω \Omega Ω Φ \Phi Φ OPT w \operatorname{OPT}_w OPT w w w w P \mathcal{P} P S S S L \mathcal{L} L S ′ ∈ Π S S' \in\Pi_S S ′ ∈ Π S Φ ( S ) − Φ ( S ′ ) ≤ ε \Phi(S) - \Phi(S') \le\varepsilon Φ ( S ) − Φ ( S ′ ) ≤ ε w ′ w' w ′ w w w S ∩ OPT w S \cap\operatorname{OPT}_w S ∩ OPT w Φ ′ \Phi' Φ ′
Φ ′ ( S ∩ OPT w ) ≤ Λ 2 w ′ ( S ∩ OPT w ) = 0. \Phi'(S \cap\operatorname{OPT}_w) \le\Lambda_2 w'(S \cap\operatorname{OPT}_w) = 0. Φ ′ ( S ∩ OPT w ) ≤ Λ 2 w ′ ( S ∩ OPT w ) = 0. Thus, for all moves S ′ ∈ Π S S' \in\Pi_S S ′ ∈ Π S Φ ′ ( S ) − Φ ′ ( S ′ ) ≤ ε \Phi'(S) - \Phi'(S') \le\varepsilon Φ ′ ( S ) − Φ ′ ( S ′ ) ≤ ε S S S Φ ′ \Phi' Φ ′ γ \gamma γ w ′ ( S ) ≤ γ w ′ ( OPT w ) w'(S) \le\gamma w'(\operatorname{OPT}_w) w ′ ( S ) ≤ γ w ′ ( OPT w ) w ′ w' w ′
w ( S ∖ OPT w ) ≤ γ w ( OPT w ∖ S ) . w(S \setminus\operatorname{OPT}_w) \le\gamma w(\operatorname{OPT}_w \setminus S). w ( S ∖ OPT w ) ≤ γ w ( OPT w ∖ S ) . Minimal Move Covering
We now need a property that links the cost of a current solution S S S T T T Π S \Pi_S Π S S S S Π S T ⊆ Π S \Pi^T_S \subseteq\Pi_S Π S T ⊆ Π S S ′ S' S ′ ( S ′ ∖ S ) ∩ T ≠ ∅ (S' \setminus S) \cap T \ne\varnothing ( S ′ ∖ S ) ∩ T = ∅ ( S ′ ∖ S ) ⊆ T (S' \setminus S) \subseteq T ( S ′ ∖ S ) ⊆ T S ′ S' S ′ T T T S S S T T T Φ ( S ) \Phi(S) Φ ( S ) Φ ( T ) \Phi(T) Φ ( T ) Π S T \Pi^T_S Π S T S S S T T T
Property 9 (Minimal Move Covering). Let d ∈ N d \in\mathbb{N} d ∈ N L \mathcal{L} L d d d S S S T T T α : Π S T → R + \alpha: \Pi^T_S \to\mathbb{R}^+ α : Π S T → R +
For all i ∈ S ∖ T i \in S \setminus T i ∈ S ∖ T ∑ S ′ ∈ Π S T : i ∈ S ′ ∖ S α ( S ′ ) ≥ 1 \sum_{S' \in\Pi^T_S: i \in S' \setminus S} \alpha(S') \ge1 ∑ S ′ ∈ Π S T : i ∈ S ′ ∖ S α ( S ′ ) ≥ 1 S S S
For all i ∈ T ∖ S i \in T \setminus S i ∈ T ∖ S ∑ S ′ ∈ Π S T : i ∈ S ′ ∖ S α ( S ′ ) ≤ d \sum_{S' \in\Pi^T_S: i \in S' \setminus S} \alpha(S') \le d ∑ S ′ ∈ Π S T : i ∈ S ′ ∖ S α ( S ′ ) ≤ d T T T
∑ S ′ ∈ Π S T α ( S ′ ) ≤ n \sum_{S' \in\Pi^T_S} \alpha(S') \le n ∑ S ′ ∈ Π S T α ( S ′ ) ≤ n
The goal here is to have d d d d ≥ λ d \ge\lambda d ≥ λ λ \lambda λ P \mathcal{P} P λ \lambda λ d d d
Surprisingly, the d d d 1 / θ 1/\theta 1/ θ ≤ λ \le\lambda ≤ λ ρ ( S , S ′ ) = Φ ( S ∖ S ′ ) Φ ( S ′ ∖ S ) \rho(S,S') = \frac{\Phi(S\setminus S')}{\Phi(S'\setminus S)} ρ ( S , S ′ ) = Φ ( S ′ ∖ S ) Φ ( S ∖ S ′ ) Φ ( S ∖ S ′ ) \Phi(S\setminus S') Φ ( S ∖ S ′ ) Φ ( S ′ ∖ S ) \Phi(S'\setminus S) Φ ( S ′ ∖ S ) S ′ ∈ Π S T S' \in\Pi_S^T S ′ ∈ Π S T Φ ( S ∖ S ′ ) \Phi(S\setminus S') Φ ( S ∖ S ′ ) S S S S ′ S' S ′ S S S S ′ S' S ′ Φ ( S ′ ∖ S ) \Phi(S'\setminus S) Φ ( S ′ ∖ S ) T T T d d d
Lemma 10. Let S , T S,T S , T Φ \Phi Φ λ , θ ≥ 1 \lambda,\theta\ge1 λ , θ ≥ 1
∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ∖ S ′ ) ≥ 1 θ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ∖ S ′ ) . \sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S\setminus S') \ge\frac{1}{\theta}\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S\setminus S'). S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ∖ S ′ ) ≥ θ 1 S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ∖ S ′ ) . If the d d d Φ ( S ∖ T ) ≤ d θ λ Φ ( T ∖ S ) \Phi(S\setminus T) \le d\theta\lambda\Phi(T\setminus S) Φ ( S ∖ T ) ≤ d θ λ Φ ( T ∖ S )
Proof. Assume that
∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ∖ S ′ ) ≥ 1 θ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ∖ S ′ ) . \sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S\setminus S') \ge\frac{1}{\theta}\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S\setminus S'). S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ∖ S ′ ) ≥ θ 1 S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ∖ S ′ ) . We start by forming the following expression, summing over every move S ′ ∈ Π S T S' \in\Pi_S^T S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ \rho(S,S') \le\lambda ρ ( S , S ′ ) ≤ λ
σ = ∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ′ ∖ S ) − 1 λ ∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ∖ S ′ ) . \sigma= \sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S'\setminus S) - \frac{1}{\lambda}\sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S\setminus S'). σ = S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ′ ∖ S ) − λ 1 S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ∖ S ′ ) . From the hypothesis, we have:
σ ≤ ∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ′ ∖ S ) − 1 θ λ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ∖ S ′ ) ≤ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ′ ∖ S ) − 1 θ λ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ∖ S ′ ) . \begin{aligned}
\sigma\le\sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S'\setminus S) - \frac{1}{\theta\lambda}\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S\setminus S') \\
&\le\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S'\setminus S) - \frac{1}{\theta\lambda}\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S\setminus S').
\end{aligned} σ ≤ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ′ ∖ S ) − θ λ 1 S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ∖ S ′ ) ≤ S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ′ ∖ S ) − θ λ 1 S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ∖ S ′ ) . And also, since
∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ′ ∖ S ) ≥ 1 λ ∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ∖ S ′ ) \sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S'\setminus S) \ge\frac{1}{\lambda}\sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S\setminus S') S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ′ ∖ S ) ≥ λ 1 S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ∖ S ′ ) we have
σ ≥ 1 λ ∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ∖ S ′ ) − 1 λ ∑ S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ α ( S ′ ) Φ ( S ∖ S ′ ) = 0. \sigma\ge\frac{1}{\lambda}\sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S\setminus S') - \frac{1}{\lambda}\sum_{\substack{S' \in\Pi_S^T\\ \rho(S,S') \le\lambda}} \alpha(S')\Phi(S\setminus S') = 0. σ ≥ λ 1 S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ∖ S ′ ) − λ 1 S ′ ∈ Π S T ρ ( S , S ′ ) ≤ λ ∑ α ( S ′ ) Φ ( S ∖ S ′ ) = 0. Therefore, we have:
∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ′ ∖ S ) ≥ 1 θ λ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ∖ S ′ ) . \sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S'\setminus S) \ge\frac{1}{\theta\lambda}\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S\setminus S'). S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ′ ∖ S ) ≥ θ λ 1 S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ∖ S ′ ) . Now, using the d d d Π S T \Pi_S^T Π S T
∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ′ ∖ S ) = ∑ i ∈ T ∖ S ϕ ( i ) ∑ S ′ ∈ Π S T i ∈ S ′ ∖ S α ( S ′ ) = ∑ i ∈ T ∖ S ϕ ( i ) ∑ S ′ ∈ Π S T i ∈ S ′ ∖ S α ( S ′ ) ≤ d Φ ( T ∖ S ) (by (2) of d -MMC). \begin{aligned}
\sum_{S' \in\Pi_S^T} \alpha(S')\Phi(S'\setminus S) = \sum_{i \in T\setminus S} \phi(i)\sum_{\substack{S' \in\Pi_S^T\\ i \in S'\setminus S}} \alpha(S') \\
&= \sum_{i \in T\setminus S} \phi(i)\sum_{\substack{S' \in\Pi_S^T\\ i \in S'\setminus S}} \alpha(S') \le d\Phi(T\setminus S)\quad\text{(by (2) of $d$-MMC).}
\end{aligned} S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ′ ∖ S ) = i ∈ T ∖ S ∑ ϕ ( i ) S ′ ∈ Π S T i ∈ S ′ ∖ S ∑ α ( S ′ ) = i ∈ T ∖ S ∑ ϕ ( i ) S ′ ∈ Π S T i ∈ S ′ ∖ S ∑ α ( S ′ ) ≤ d Φ ( T ∖ S ) (by (2) of d -MMC). Now, with the right-hand side, the argument is similar:
1 θ λ ∑ S ′ ∈ Π S T α ( S ′ ) Φ ( S ∖ S ′ ) = 1 θ λ ∑ i ∈ S ∑ S ′ ∈ Π S T i ∈ S ∖ S ′ α ( S ′ ) ϕ ( i ) ≥ 1 θ λ ∑ i ∈ S ∖ T ϕ ( i ) ∑ S ′ ∈ Π S T i ∈ S ∖ S ′ α ( S ′ ) ≥ 1 θ λ Φ ( S ∖ T ) (by (1) of the d -MMC property). \begin{aligned}
\frac{1}{\theta\lambda}\sum_{S'\in\Pi_S^T}\alpha(S')\Phi(S\setminus S')=\frac{1}{\theta\lambda}\sum_{i\in S}\sum_{\substack{S'\in\Pi_S^T\\i\in S\setminus S'}}\alpha(S')\phi(i)\ge\frac{1}{\theta\lambda}\sum_{i\in S\setminus T}\phi(i)\sum_{\substack{S'\in\Pi_S^T\\i\in S\setminus S'}}\alpha(S') \\
&\ge\frac{1}{\theta\lambda}\Phi(S\setminus T)\quad\text{(by (1) of the $d$-MMC property).}
\end{aligned} θ λ 1 S ′ ∈ Π S T ∑ α ( S ′ ) Φ ( S ∖ S ′ ) = θ λ 1 i ∈ S ∑ S ′ ∈ Π S T i ∈ S ∖ S ′ ∑ α ( S ′ ) ϕ ( i ) ≥ θ λ 1 i ∈ S ∖ T ∑ ϕ ( i ) S ′ ∈ Π S T i ∈ S ∖ S ′ ∑ α ( S ′ ) ≥ θ λ 1 Φ ( S ∖ T ) (by (1) of the d -MMC property). This concludes: d θ λ Φ ( T ∖ S ) ≥ Φ ( S ∖ T ) d\theta\lambda\Phi(T\setminus S)\ge\Phi(S\setminus T) d θ λ Φ ( T ∖ S ) ≥ Φ ( S ∖ T )
This will be used as follows: as long as we do not have a satisfying difference-approximation, there will be many moves that add some parts of the optimal solution which are “good” in the sense that they significantly decrease the potential.
This implies the following lemma that will be the version used in the analysis of the algorithm to show that the algorithm makes progress. In the following, we assume that L \mathcal{L} L d d d
Lemma 11 (generalizes Lemma 5.10 from [6 ] ). Let S S S T T T P P P Φ \Phi Φ Φ ′ \Phi' Φ ′ Γ > 1 \Gamma>1 Γ > 1 Φ ( S ∖ T ) > d Γ Φ ′ ( T ∖ S ) \Phi(S\setminus T)>d\Gamma\Phi'(T\setminus S) Φ ( S ∖ T ) > d Γ Φ ′ ( T ∖ S ) ϵ ∈ ( 0 , Γ − 1 ) \epsilon\in(0,\sqrt{\Gamma}-1) ϵ ∈ ( 0 , Γ − 1 ) S ′ ∈ Π S T S'\in\Pi_S^T S ′ ∈ Π S T r = S ∖ S ′ r=S\setminus S' r = S ∖ S ′ a = S ′ ∖ S a=S'\setminus S a = S ′ ∖ S
( 1 + ϵ ) Φ ′ ( a ) − Φ ′ ( r ) Φ ( r ) − ( 1 + ϵ ) Φ ( a ) ≤ d ( 1 + ϵ ) Γ ( Γ − 1 ) ( Γ − 1 − ϵ ) Φ ′ ( T ∖ S ) Φ ( S ∖ T ) \frac{(1+\epsilon)\Phi'(a)-\Phi'(r)}{\Phi(r)-(1+\epsilon)\Phi(a)}\le\frac{d(1+\epsilon)\Gamma}{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\epsilon)}\frac{\Phi'(T\setminus S)}{\Phi(S\setminus T)} Φ ( r ) − ( 1 + ϵ ) Φ ( a ) ( 1 + ϵ ) Φ ′ ( a ) − Φ ′ ( r ) ≤ ( Γ − 1 ) ( Γ − 1 − ϵ ) d ( 1 + ϵ ) Γ Φ ( S ∖ T ) Φ ′ ( T ∖ S ) and Φ ( r ) − ( 1 + ϵ ) Φ ( a ) ≥ 1 n 2 Φ ( S ∖ T ) \Phi(r)-(1+\epsilon)\Phi(a)\ge\frac{1}{n^2}\Phi(S\setminus T) Φ ( r ) − ( 1 + ϵ ) Φ ( a ) ≥ n 2 1 Φ ( S ∖ T )
Proof. With S S S r S ′ = S ∖ S ′ r_{S'}=S\setminus S' r S ′ = S ∖ S ′ a S ′ = S ′ ∖ S a_{S'}=S'\setminus S a S ′ = S ′ ∖ S
We follow the averaging argument of [6 ] . Consider the quantity:
R = ∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ 1 n 2 Φ ( S ∖ T ) α ( S ′ ) [ ( 1 + ϵ ) Φ ′ ( a S ′ ) − Φ ′ ( r S ′ ) ] ∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ 1 n 2 Φ ( S ∖ T ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ] , R=\frac{\sum_{\substack{S'\in\Pi_S^T\\\Phi'(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})\\\Phi(r_{S'})-(1+\epsilon)\Phi(a_{S'})\ge\frac{1}{n^2}\Phi(S\setminus T)}}\alpha(S')\left[(1+\epsilon)\Phi'(a_{S'})-\Phi'(r_{S'})\right]}{\sum_{\substack{S'\in\Pi_S^T\\\Phi'(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})\\\Phi(r_{S'})-(1+\epsilon)\Phi(a_{S'})\ge\frac{1}{n^2}\Phi(S\setminus T)}}\alpha(S')\left[\Phi(r_{S'})-(1+\epsilon)\Phi(a_{S'})\right]}, R = ∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ n 2 1 Φ ( S ∖ T ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ] ∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ n 2 1 Φ ( S ∖ T ) α ( S ′ ) [ ( 1 + ϵ ) Φ ′ ( a S ′ ) − Φ ′ ( r S ′ ) ] , which we want to upper bound. We start by bounding the numerator by d ( 1 + ϵ ) Φ ′ ( T ∖ S ) d(1+\epsilon)\Phi'(T\setminus S) d ( 1 + ϵ ) Φ ′ ( T ∖ S )
∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ 1 n 2 Φ ( S ∖ T ) α ( S ′ ) [ ( 1 + ϵ ) Φ ′ ( a S ′ ) − Φ ′ ( r S ′ ) ] ≤ ( 1 + ϵ ) ∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ 1 n 2 Φ ( S ∖ T ) α ( S ′ ) Φ ′ ( a S ′ ) = ( 1 + ϵ ) ∑ i ∈ T ∖ S ϕ ′ ( i ) ∑ S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ 1 n 2 Φ ( S ∖ T ) i ∈ a S ′ α ( S ′ ) ≤ ( 1 + ϵ ) d Φ ′ ( T ∖ S ) . \begin{aligned}
&\sum_{\substack{S'\in\Pi_S^T\\\Phi'(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})\\\Phi(r_{S'})-(1+\epsilon)\Phi(a_{S'})\ge\frac{1}{n^2}\Phi(S\setminus T)}}\alpha(S')\left[(1+\epsilon)\Phi'(a_{S'})-\Phi'(r_{S'})\right]\\
&\le(1+\epsilon)\sum_{\substack{S'\in\Pi_S^T\\\Phi'(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})\\\Phi(r_{S'})-(1+\epsilon)\Phi(a_{S'})\ge\frac{1}{n^2}\Phi(S\setminus T)}}\alpha(S')\Phi'(a_{S'})\\
&=(1+\epsilon)\sum_{i\in T\setminus S}\phi'(i)\sum_{\substack{S'\in\Pi_S^T\\\Phi'(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})\\\Phi(r_{S'})-(1+\epsilon)\Phi(a_{S'})\ge\frac{1}{n^2}\Phi(S\setminus T)\\i\in a_{S'}}}\alpha(S')\\
&\le(1+\epsilon)d\Phi'(T\setminus S).
\end{aligned} S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ n 2 1 Φ ( S ∖ T ) ∑ α ( S ′ ) [ ( 1 + ϵ ) Φ ′ ( a S ′ ) − Φ ′ ( r S ′ ) ] ≤ ( 1 + ϵ ) S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ n 2 1 Φ ( S ∖ T ) ∑ α ( S ′ ) Φ ′ ( a S ′ ) = ( 1 + ϵ ) i ∈ T ∖ S ∑ ϕ ′ ( i ) S ′ ∈ Π S T Φ ′ ( r S ′ ) > Γ Φ ( a S ′ ) Φ ( r S ′ ) − ( 1 + ϵ ) Φ ( a S ′ ) ≥ n 2 1 Φ ( S ∖ T ) i ∈ a S ′ ∑ α ( S ′ ) ≤ ( 1 + ϵ ) d Φ ′ ( T ∖ S ) . The second to last equality comes from the fact that by definition, for every move S ′ S' S ′ a S ′ ∩ S = ∅ a_{S'} \cap S = \varnothing a S ′ ∩ S = ∅
Now, we lower bound the denominator. Observe that:
∑ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] ≥ ∑ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] − ∑ S ′ ∈ Π T s Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) < 1 n 2 Φ ( S ∖ T ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] . \sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})}} \alpha(S')\left[\Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})\right]
\ge
\sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})}} \alpha(S')\left[\Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})\right]
-
\sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})<\frac{1}{n^2}\Phi(S\setminus T)}} \alpha(S')\left[\Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})\right]. S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) ∑ α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] ≥ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) ∑ α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] − S ′ ∈ Π T s Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) < n 2 1 Φ ( S ∖ T ) ∑ α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] . We start by upper bounding the second term of the right-hand side of the equation above:
∑ S ′ ∈ Π T s Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) < 1 n 2 Φ ( S ∖ T ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] ≤ 1 n 2 Φ ( S ∖ T ) ∑ S ′ ∈ Π T s Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) < 1 n 2 Φ ( S ∖ T ) α ( S ′ ) ≤ Φ ( S ∖ T ) n \sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})<\frac{1}{n^2}\Phi(S\setminus T)}} \alpha(S')\left[\Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})\right]
\le\frac{1}{n^2}\Phi(S\setminus T)
\sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})<\frac{1}{n^2}\Phi(S\setminus T)}}\alpha(S')
\le\frac{\Phi(S\setminus T)}{n} S ′ ∈ Π T s Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) < n 2 1 Φ ( S ∖ T ) ∑ α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] ≤ n 2 1 Φ ( S ∖ T ) S ′ ∈ Π T s Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) < n 2 1 Φ ( S ∖ T ) ∑ α ( S ′ ) ≤ n Φ ( S ∖ T ) by condition (3) of the d d d
We will now use Lemma 10 (with λ = θ = Γ \lambda=\theta=\sqrt{\Gamma} λ = θ = Γ
∑ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] ≥ ∑ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) α ( S ′ ) [ Φ ( r S ′ ) − 1 + ε Γ Φ ( r S ′ ) ] = Γ − 1 − ε Γ ∑ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) α ( S ′ ) Φ ( r S ′ ) ≥ ( Γ − 1 ) ( Γ − 1 − ε ) Γ ∑ S ′ ∈ Π T s α ( S ′ ) Φ ( r S ′ ) . \sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})}} \alpha(S')\left[\Phi(r_{S'})-(1+\varepsilon)\Phi(a_{S'})\right]
\ge
\sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})}} \alpha(S')\left[\Phi(r_{S'})-\frac{1+\varepsilon}{\sqrt{\Gamma}}\Phi(r_{S'})\right]
=
\frac{\sqrt{\Gamma}-1-\varepsilon}{\sqrt{\Gamma}}
\sum_{\substack{S'\in\Pi_T^s\\ \Phi(r_{S'})>\sqrt{\Gamma}\Phi(a_{S'})}} \alpha(S')\Phi(r_{S'})
\ge
\frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{\Gamma}
\sum_{S'\in\Pi_T^s}\alpha(S')\Phi(r_{S'}). S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) ∑ α ( S ′ ) [ Φ ( r S ′ ) − ( 1 + ε ) Φ ( a S ′ ) ] ≥ S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) ∑ α ( S ′ ) [ Φ ( r S ′ ) − Γ 1 + ε Φ ( r S ′ ) ] = Γ Γ − 1 − ε S ′ ∈ Π T s Φ ( r S ′ ) > Γ Φ ( a S ′ ) ∑ α ( S ′ ) Φ ( r S ′ ) ≥ Γ ( Γ − 1 ) ( Γ − 1 − ε ) S ′ ∈ Π T s ∑ α ( S ′ ) Φ ( r S ′ ) . We show that ∑ S ′ ∈ Π T s α ( S ′ ) Φ ( r S ′ ) ≥ Φ ( S ∖ T ) \sum_{S'\in\Pi_T^s}\alpha(S')\Phi(r_{S'})\ge\Phi(S\setminus T) ∑ S ′ ∈ Π T s α ( S ′ ) Φ ( r S ′ ) ≥ Φ ( S ∖ T )
∑ S ′ ∈ Π T s α ( S ′ ) Φ ( r S ′ ) = ∑ i ∈ S φ ( i ) ∑ S ′ ∈ Π T s i ∈ r S ′ α ( S ′ ) ≥ ∑ i ∈ S φ ( i ) = Φ ( S ) ≥ Φ ( S ∖ T ) . \sum_{S'\in\Pi_T^s}\alpha(S')\Phi(r_{S'})
=
\sum_{i\in S}\varphi(i)\sum_{\substack{S'\in\Pi_T^s\\ i\in r_{S'}}}\alpha(S')
\ge
\sum_{i\in S}\varphi(i)
=
\Phi(S)
\ge
\Phi(S\setminus T). S ′ ∈ Π T s ∑ α ( S ′ ) Φ ( r S ′ ) = i ∈ S ∑ φ ( i ) S ′ ∈ Π T s i ∈ r S ′ ∑ α ( S ′ ) ≥ i ∈ S ∑ φ ( i ) = Φ ( S ) ≥ Φ ( S ∖ T ) . Therefore, we conclude that:
R ≤ ( 1 + ε ) d ( Γ − 1 ) ( Γ − 1 − ε ) Γ − 1 n Φ ′ ( T ∖ S ) Φ ( S ∖ T ) . R\le
\frac{(1+\varepsilon)d}
{\frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{\Gamma}-\frac{1}{n}}
\frac{\Phi'(T\setminus S)}{\Phi(S\setminus T)}. R ≤ Γ ( Γ − 1 ) ( Γ − 1 − ε ) − n 1 ( 1 + ε ) d Φ ( S ∖ T ) Φ ′ ( T ∖ S ) . and the result follows for n n n
Efficient Good Move Retrieval
We want to be able to find a move that is good enough, i.e. , that is close to being as good (for both potentials Φ \Phi Φ Φ ′ \Phi' Φ ′
Property 12 (generalizes Lemma 5.11 of [6 ] ). Let ε > 0 \varepsilon> 0 ε > 0 Φ \Phi Φ Φ ′ \Phi' Φ ′ S S S W , W ′ > 0 W,W' > 0 W , W ′ > 0 S ′ ∈ Π S S' \in\Pi_S S ′ ∈ Π S Φ ( S ′ ∖ S ) − Φ ( S ∖ S ′ ) ≤ W \Phi(S' \setminus S) - \Phi(S \setminus S') \le W Φ ( S ′ ∖ S ) − Φ ( S ∖ S ′ ) ≤ W Φ ′ ( S ′ ∖ S ) − Φ ′ ( S ∖ S ′ ) ≤ W ′ \Phi'(S' \setminus S) - \Phi'(S \setminus S') \le W' Φ ′ ( S ′ ∖ S ) − Φ ′ ( S ∖ S ′ ) ≤ W ′ S ′ ′ S'' S ′′
Φ ( S ′ ′ ∖ S ) − Φ ( S ∖ S ′ ′ ) ≤ ( 1 + ε ) W \Phi(S'' \setminus S) - \Phi(S \setminus S'') \le(1+\varepsilon)W Φ ( S ′′ ∖ S ) − Φ ( S ∖ S ′′ ) ≤ ( 1 + ε ) W
Φ ′ ( S ′ ′ ∖ S ) − Φ ′ ( S ∖ S ′ ′ ) ≤ ( 1 + ε ) W ′ \Phi'(S'' \setminus S) - \Phi'(S \setminus S'') \le(1+\varepsilon)W' Φ ′ ( S ′′ ∖ S ) − Φ ′ ( S ∖ S ′′ ) ≤ ( 1 + ε ) W ′
The robust approximation algorithm
We show that a local search that satisfies the three required properties Property 6, Property 9 and Property 12 of the previous subsection can be used to get a robust approximation algorithm by providing an ASO for the LP formulation of P R \mathcal{P}_R P R Theorem 2 .
We follow the idea of alternate minimization from [6 ] , which optimizes a solution over two different weight functions by alternating between a forward phase and a backward phase, both concentrated on optimizing one weight function while ensuring that the other does not get out of control. For both phases, the GreedySwap algorithm 3 extracts a “good move” using the efficient good move retrieval property of the local search. The DoubleApprox algorithm 2 is essentially the same as in [6 ] , with potentials instead of weight functions, and some constants changed to d d d Λ \Lambda Λ P \mathcal{P} P
Analysis of the algorithm
We can now turn to proving the main theorem of this paper:
Theorem 13 (generalizes Theorem 5.1 of [6 ] ). Let P \mathcal{P} P L \mathcal{L} L Λ \Lambda Λ d d d P \mathcal{P} P λ \lambda λ P \mathcal{P} P δ \delta δ
Then, the robust version of problem P \mathcal{P} P ( 17 λ δ d Λ [ 2 Λ ( 9 d + 1 ) + 1 ] + λ δ , λ [ 17 δ d Λ + 1 ] ) (17\lambda\delta d\Lambda[2\Lambda(9d+1)+1]+\lambda\delta,\lambda[17\delta d\Lambda+1]) ( 17 λ δ d Λ [ 2Λ ( 9 d + 1 ) + 1 ] + λ δ , λ [ 17 δ d Λ + 1 ])
This is the most technical section of the paper. Its goal is to rewrite the proofs used in [6 ] in a way that makes them more general. We therefore also use their idea of a double-approximation algorithm DoubleApprox (Algorithm 2). The analysis of this algorithm necessitates a number of very technical lemmas, so we will provide an overview of the way they work together. Some proofs are deferred to the appendix when they are too long and very similar to the ones from [6 ] .
In this section, we will consider that we are in the ( α , β ) (\alpha,\beta) ( α , β ) α \alpha α β \beta β ( x , r ) (x,r) ( x , r ) w S O L ∈ [ ℓ , u ] w_{\mathrm{SOL}} \in[\ell,u] w SOL ∈ [ ℓ , u ] w S O L ( x ) > α w S O L ( S O L ) + β r w_{\mathrm{SOL}}(x) > \alpha w_{\mathrm{SOL}}(\mathrm{SOL})+\beta r w SOL ( x ) > α w SOL ( SOL ) + β r w S O L w_{\mathrm{SOL}} w SOL A L G j \mathrm{ALG}_j ALG j w A L G j ∈ [ ℓ , u ] w_{\mathrm{ALG}_j} \in[\ell,u] w ALG j ∈ [ ℓ , u ] w A L G j ( x ) > w A L G j ( A L G j ) + r w_{\mathrm{ALG}_j}(x) > w_{\mathrm{ALG}_j}(\mathrm{ALG}_j)+r w ALG j ( x ) > w ALG j ( ALG j ) + r
Our goal is to get to Lemma 15, which is stated below, and shows that algorithm DoubleApprox returns a polynomial-size set of solutions, one of which satisfies two approximation constraints on two weight vectors w w w w ′ w' w ′
Now, let’s give some intuition about the way DoubleApprox works. A detailed overview can be found in [6 ] (Section 5.2); we provide a summary of the idea in the following paragraph.
Data: A set Ω \Omega Ω Φ \Phi Φ Φ ′ \Phi' Φ ′ ϕ ( i ) \phi^{(i)} ϕ ( i ) ε n χ \frac{\varepsilon}{n}\chi n ε χ χ > 0 \chi>0 χ > 0 χ ∈ [ Φ ( S O L ) , 1 + ε ⋅ Φ ( S O L ) ] \chi\in[\Phi(\mathrm{SOL}),\sqrt{1+\varepsilon}\cdot\Phi(\mathrm{SOL})] χ ∈ [ Φ ( SOL ) , 1 + ε ⋅ Φ ( SOL )] χ ′ > 0 \chi'>0 χ ′ > 0 χ ′ ∈ [ Φ ′ ( S O L ) , 1 + ε ⋅ Φ ′ ( S O L ) ] \chi'\in[\Phi'(\mathrm{SOL}),\sqrt{1+\varepsilon}\cdot\Phi'(\mathrm{SOL})] χ ′ ∈ [ Φ ′ ( SOL ) , 1 + ε ⋅ Φ ′ ( SOL )] Γ , Γ ′ , κ , d , ε \Gamma,\Gamma',\kappa,d,\varepsilon Γ , Γ ′ , κ , d , ε
1 i ← 0
/* The following constants are used to guarantee polynomial-time termination */
2 ζ' ← d^{(1+ε)Γ'} / ((√Γ'−1)(√Γ'−1−ε)(dΓ'−1)(dΓ−1))
3 η ← min { [ dΓ−1 / (2dΓ), (dΓ−1)(√Γ−1)(√Γ−1−ε)κ / (d²(1+ε)Γ²) ] − (e^{ε'(dΓ'+κ+1+ε)}−1) } / [1 + dΓ/(dΓ−1)(e^{ε'(dΓ'+κ+1+ε)}−1)]
4 I ← 2(⌈log (n max_{i∈Ω} φ(i) / min_{i∈Ω, φ(i)>0} φ(i)) / log(1+η)⌉ + 1)
5 ALG^(0) ← λ-approximation of optimal solution with respect to Φ' for λ < dΓ'
6 while i ≤ I do
/* Iterate over all guesses ρ for Φ(ALG^(i) \ SOL) */
7 m ← min_{i∈Ω, φ(i)>0} φ(i)
8 for ρ ∈ {m,(1+ε)m,...,(1+ε)^{⌈log_{1+ε}(n/m max_{i∈Ω} φ(i))⌉}m} do
9 ALG_ρ^(i+1) ← ALG^(i)
/* Forward phase */
10 while Φ'(ALG_ρ^(i+1)) ≤ (dΓ' + κ)χ' and Φ(ALG_ρ^(i+1)) > Φ(ALG^(i)) − ρ/2 do
11 (ALG_ρ^(i+1), stop) ← GreedySwap(ALG_ρ^(i+1), Φ, Φ', χ, χ', 1/(10n²)ρ)
12 if stop = 1 then
13 break while loop starting on Line 10
14 ALG_ρ^(i+2) ← ALG_ρ^(i+1)
/* Backward phase */
15 while Φ'(ALG_ρ^(i+2)) ≥ dΓ'χ' do
16 (ALG_ρ^(i+2), ∼) ← GreedySwap(ALG_ρ^(i+2), Φ', Φ, χ', χ, ε/n χ')
/* If Φ(ALG^(i) \ SOL) = 0, then ALG^(i) satisfies Lemma 15 */
17 ALG_0^(i+2) ← ALG^(i)
18 ALG^(i+2) ← argmin_ρ Φ(ALG_ρ^(i+2))
19 i ← i + 2
20 return all values of ALG_ρ^(i) stored for any value of i, ρAlgorithm 2: DoubleApprox ( Ω , Φ , Φ ′ , χ , χ ′ , Γ , Γ ′ , κ ) (\Omega,\Phi,\Phi',\chi,\chi',\Gamma,\Gamma',\kappa) ( Ω , Φ , Φ ′ , χ , χ ′ , Γ , Γ ′ , κ ) [6 ] adapted to our notation, uses the local search algorithm L \mathcal{L} L Φ \Phi Φ Φ ′ \Phi' Φ ′
What the DoubleApprox algorithm does is that assuming two ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) χ \chi χ Φ ( S O L ) \Phi(\mathrm{SOL}) Φ ( SOL ) χ ′ \chi' χ ′ Φ ′ ( S O L ) \Phi'(\mathrm{SOL}) Φ ′ ( SOL ) A L G ( i ) \mathrm{ALG}^{(i)} ALG ( i ) Φ ( A L G ( i ) ∖ S O L ) \Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL}) Φ ( ALG ( i ) ∖ SOL ) ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) Φ \Phi Φ Φ ′ \Phi' Φ ′ χ \chi χ χ ′ \chi' χ ′
Remark 14. The case where Φ ( S O L ) = 0 \Phi(\mathrm{SOL})=0 Φ ( SOL ) = 0 Φ ′ ( S O L ) = 0 \Phi'(\mathrm{SOL})=0 Φ ′ ( SOL ) = 0 max i ∈ Ω ϕ ( i ) > 0 \max_{i\in\Omega}\phi(i)>0 max i ∈ Ω ϕ ( i ) > 0
Lemma 15 (generalizes Lemma 5.5 of [6 ] ). Let S O L \mathrm{SOL} SOL P P P ( x , x ′ ) (x,x') ( x , x ′ ) x x x w w w w ′ w' w ′ w i = u i x i + ℓ i ( 1 − x i ) w_i=u_ix_i+\ell_i(1-x_i) w i = u i x i + ℓ i ( 1 − x i ) w i ′ = ℓ i ( 1 − x i ) w'_i=\ell_i(1-x_i) w i ′ = ℓ i ( 1 − x i ) Γ ′ > 1 \Gamma'>1 Γ ′ > 1 κ > 0 \kappa>0 κ > 0 0 < ε < 1 / 4 0<\varepsilon<1/4 0 < ε < 1/4 Γ \Gamma Γ A L G \mathrm{ALG} ALG A L G j \mathrm{ALG}_j ALG j
Data: Solution ALG, potential functions Φ \Phi Φ Φ ′ \Phi' Φ ′ χ ∈ [ Φ ( S O L ) , 1 + ε Φ ( S O L ) ] \chi\in[\Phi(\mathrm{SOL}),\sqrt{1+\varepsilon}\Phi(\mathrm{SOL})] χ ∈ [ Φ ( SOL ) , 1 + ε Φ ( SOL )] χ > 0 \chi> 0 χ > 0 χ ′ ∈ [ Φ ′ ( S O L ) , 1 + ε Φ ′ ( S O L ) ] \chi' \in[\Phi'(\mathrm{SOL}),\sqrt{1+\varepsilon}\Phi'(\mathrm{SOL})] χ ′ ∈ [ Φ ′ ( SOL ) , 1 + ε Φ ′ ( SOL )] χ ′ > 0 \chi' > 0 χ ′ > 0 ρ \rho ρ
T ← ∅ \mathcal{T} \leftarrow\emptyset T ← ∅
m ← min i ∈ Ω , ϕ ( i ) > 0 ϕ ( i ) m \leftarrow\min_{i\in\Omega,\ \phi(i)>0}\phi(i) m ← min i ∈ Ω , ϕ ( i ) > 0 ϕ ( i )
m ′ ← min i ∈ Ω , ϕ ′ ( i ) > 0 ϕ ′ ( i ) m' \leftarrow\min_{i\in\Omega,\ \phi'(i)>0}\phi'(i) m ′ ← min i ∈ Ω , ϕ ′ ( i ) > 0 ϕ ′ ( i )
for W ∈ { m , 1 + ε m , … , 1 + ε ⌈ log 1 + ε χ ⌉ m } W \in\{m,\sqrt{1+\varepsilon}m,\ldots,\sqrt{1+\varepsilon}^{\lceil\log_{1+\varepsilon}\chi\rceil}m\} W ∈ { m , 1 + ε m , … , 1 + ε ⌈ l o g 1 + ε χ ⌉ m } do
for W ′ ∈ { m ′ , 1 + ε m ′ , … , 1 + ε ⌈ log 1 + ε χ ′ ⌉ m ′ } W' \in\{m',\sqrt{1+\varepsilon}m',\ldots,\sqrt{1+\varepsilon}^{\lceil\log_{\sqrt{1+\varepsilon}}\chi'\rceil}m'\} W ′ ∈ { m ′ , 1 + ε m ′ , … , 1 + ε ⌈ l o g 1 + ε χ ′ ⌉ m ′ } do
Using Property 12, try to find a move S ′ ∈ Π A L G S' \in\Pi_{\mathrm{ALG}} S ′ ∈ Π ALG Φ ( S ′ ∖ A L G ) − Φ ( A L G ∖ S ′ ) ≤ 1 + ε W \Phi(S'\setminus\mathrm{ALG})-\Phi(\mathrm{ALG}\setminus S')\le\sqrt{1+\varepsilon}W Φ ( S ′ ∖ ALG ) − Φ ( ALG ∖ S ′ ) ≤ 1 + ε W Φ ′ ( S ′ ∖ A L G ) − Φ ′ ( A L G ∖ S ′ ) ≤ 1 + ε W ′ \Phi'(S'\setminus\mathrm{ALG})-\Phi'(\mathrm{ALG}\setminus S')\le\sqrt{1+\varepsilon}W' Φ ′ ( S ′ ∖ ALG ) − Φ ′ ( ALG ∖ S ′ ) ≤ 1 + ε W ′
if move S ′ S' S ′ Φ ( A L G ∖ S ′ ) − Φ ( S ′ ∖ A L G ) ≥ ρ \Phi(\mathrm{ALG}\setminus S')-\Phi(S'\setminus\mathrm{ALG})\ge\rho Φ ( ALG ∖ S ′ ) − Φ ( S ′ ∖ ALG ) ≥ ρ then
T ← T ∪ { S ′ } \mathcal{T}\leftarrow\mathcal{T}\cup\{S'\} T ← T ∪ { S ′ }
if T = ∅ \mathcal{T}=\emptyset T = ∅ then
return ( A L G , 1 ) (\mathrm{ALG},1) ( ALG , 1 )
S ∗ ← argmin S ′ ∈ T Φ ′ ( S ′ ∖ A L G ) − Φ ′ ( A L G ∖ S ′ ) Φ ( A L G ∖ S ′ ) − Φ ( S ′ ∖ A L G ) S^*\leftarrow\operatorname*{argmin}_{S'\in\mathcal{T}}\frac{\Phi'(S'\setminus\mathrm{ALG})-\Phi'(\mathrm{ALG}\setminus S')}{\Phi(\mathrm{ALG}\setminus S')-\Phi(S'\setminus\mathrm{ALG})} S ∗ ← argmin S ′ ∈ T Φ ( ALG ∖ S ′ ) − Φ ( S ′ ∖ ALG ) Φ ′ ( S ′ ∖ ALG ) − Φ ′ ( ALG ∖ S ′ )
return ( S ∗ , 0 ) (S^*,0) ( S ∗ , 0 )
Algorithm 3: GreedySwap( A L G , Φ , Φ ′ , χ , χ ′ , ρ ) (\mathrm{ALG},\Phi,\Phi',\chi,\chi',\rho) ( ALG , Φ , Φ ′ , χ , χ ′ , ρ )
w ( A L G j ∖ S O L ) ≤ d Γ Λ ⋅ w ( S O L ∖ A L G j ) w(\mathrm{ALG}_j\setminus\mathrm{SOL})\le d\Gamma\Lambda\cdot w(\mathrm{SOL}\setminus\mathrm{ALG}_j) w ( ALG j ∖ SOL ) ≤ d ΓΛ ⋅ w ( SOL ∖ ALG j )
w ′ ( A L G j ) ≤ ( d Γ ′ + κ + 1 + ε ) Λ w ′ ( S O L ) w'(\mathrm{ALG}_j)\le(d\Gamma'+\kappa+1+\varepsilon)\Lambda w'(\mathrm{SOL}) w ′ ( ALG j ) ≤ ( d Γ ′ + κ + 1 + ε ) Λ w ′ ( SOL )
In the rest of this section, we define w , w ′ w,w' w , w ′ Φ \Phi Φ Φ ′ \Phi' Φ ′ w w w w ′ w' w ′ ϕ \phi ϕ ϕ ′ \phi' ϕ ′ Ω \Omega Ω Ω \Omega Ω Φ \Phi Φ Φ ′ \Phi' Φ ′
First, Lemma 16 and Lemma 17 provide bounds on the progress of the forward and backward phase respectively. The values of the parameters Γ , Γ ′ , κ \Gamma,\Gamma',\kappa Γ , Γ ′ , κ
Lemma 16 (Forward Phase Analysis, generalizes Lemma 5.14 of [6 ] ). For any even i i i
ρ = ( 1 + ε ) ⌈ log 1 + ε ( Φ ( A L G ( i ) ∖ S O L ) min i ∈ Ω , ϕ ( i ) > 0 ϕ ( i ) ) ⌉ min i ∈ Ω , ϕ ( i ) > 0 ϕ ( i ) \rho=(1+\varepsilon)^{\left\lceil\log_{1+\varepsilon}\left(\frac{\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL})}{\min_{i\in\Omega,\ \phi(i)>0}\phi(i)}\right)\right\rceil}\min_{i\in\Omega,\ \phi(i)>0}\phi(i) ρ = ( 1 + ε ) ⌈ l o g 1 + ε ( m i n i ∈ Ω , ϕ ( i ) > 0 ϕ ( i ) Φ ( ALG ( i ) ∖ SOL ) ) ⌉ i ∈ Ω , ϕ ( i ) > 0 min ϕ ( i ) be such that ρ ∈ [ Φ ( A L G ( i ) ∖ S O L ) , ( 1 + ε ) Φ ( A L G ( i ) ∖ S O L ) ] \rho\in[\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL}),(1+\varepsilon)\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL})] ρ ∈ [ Φ ( ALG ( i ) ∖ SOL ) , ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL )] A L G ρ ( i + 1 ) \mathrm{ALG}^{(i+1)}_\rho ALG ρ ( i + 1 ) A L G ( i ) \mathrm{ALG}^{(i)} ALG ( i ) Φ ( A L G ρ ( i + 1 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) Φ ( A L G ( i ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ( i ) ) \Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i)}) Φ ( ALG ( i ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ( i ) ) 0 < ε < 2 / 3 − 5 3 d Γ 0<\varepsilon<2/3-\frac{5}{3d\Gamma} 0 < ε < 2/3 − 3 d Γ 5 A L G ( i ) \mathrm{ALG}^{(i)} ALG ( i ) A L G ρ ( i + 1 ) \mathrm{ALG}^{(i+1)}_\rho ALG ρ ( i + 1 )
Φ ( A L G ( i ) ) − Φ ( A L G ρ ( i + 1 ) ) ≥ min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } ⋅ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) . \Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}^{(i+1)}_\rho)\ge\min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}\cdot\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL}). Φ ( ALG ( i ) ) − Φ ( ALG ρ ( i + 1 ) ) ≥ min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . Lemma 17 (Backward Phase Analysis, generalizes Lemma 5.15 of [6 ] ). Fix any even i + 2 i+2 i + 2 ρ \rho ρ A L G ρ ( i + 2 ) \mathrm{ALG}^{(i+2)}_\rho ALG ρ ( i + 2 ) Φ ( A L G ρ ( i + 2 ) ∖ S O L ) > d Γ ′ ⋅ Φ ( S O L ∖ A L G ρ ( i + 2 ) ) \Phi(\mathrm{ALG}^{(i+2)}_\rho\setminus\mathrm{SOL})>d\Gamma'\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+2)}_\rho) Φ ( ALG ρ ( i + 2 ) ∖ SOL ) > d Γ ′ ⋅ Φ ( SOL ∖ ALG ρ ( i + 2 ) ) T = Φ ′ ( A L G ρ ( i + 1 ) ) − Φ ′ ( A L G ρ ( i + 2 ) ) Φ ′ ( S O L ) T=\frac{\Phi'(\mathrm{ALG}^{(i+1)}_\rho)-\Phi'(\mathrm{ALG}^{(i+2)}_\rho)}{\Phi'(\mathrm{SOL})} T = Φ ′ ( SOL ) Φ ′ ( ALG ρ ( i + 1 ) ) − Φ ′ ( ALG ρ ( i + 2 ) ) ζ ′ = d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) \zeta'=\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)(d\Gamma'-1)(d\Gamma-1)} ζ ′ = ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) d ( 1 + ε ) Γ ′ A L G ρ ( i + 1 ) , A L G ρ ( i + 2 ) \mathrm{ALG}^{(i+1)}_\rho,\mathrm{ALG}^{(i+2)}_\rho ALG ρ ( i + 1 ) , ALG ρ ( i + 2 )
Φ ( A L G ρ ( i + 2 ) ) − Φ ( A L G ρ ( i + 1 ) ) ≤ ( e ζ ′ T − 1 ) ⋅ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) . \Phi(\mathrm{ALG}^{(i+2)}_\rho)-\Phi(\mathrm{ALG}^{(i+1)}_\rho)\le(e^{\zeta'T}-1)\cdot\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL}). Φ ( ALG ρ ( i + 2 ) ) − Φ ( ALG ρ ( i + 1 ) ) ≤ ( e ζ ′ T − 1 ) ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . The following Corollary 18, which analyzes one full forward-backward iteration, follows from the two previous lemmas and shows that one iteration improves the potential of the solution currently being developed.
Corollary 18 (generalizes Corollary 5.16 of [6 ] ). Fix any positive even value of i + 2 i+2 i + 2 DoubleApprox, and let ρ \rho ρ ρ ∈ [ Φ ( A L G ( i ) ∖ S O L ) , ( 1 + ε ) Φ ( A L G ( i ) ∖ S O L ) ] \rho\in[\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL}), (1+\varepsilon)\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL})] ρ ∈ [ Φ ( ALG ( i ) ∖ SOL ) , ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL )] Suppose all values of A L G ρ ( i + 1 ) \mathrm{ALG}_{\rho}^{(i+1)} ALG ρ ( i + 1 ) and the final value of A L G ( i ) \mathrm{ALG}^{(i)} ALG ( i ) in DoubleApprox satisfy Φ ( A L G ρ ( i + 1 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+1)}\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho}^{(i+1)}) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) and Φ ( A L G ( i ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ( i ) ) \Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i)}) Φ ( ALG ( i ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ( i ) ) Then for 0 < ε < 2 3 − 5 3 d Γ 0<\varepsilon<\frac{2}{3}-\frac{5}{3d\Gamma} 0 < ε < 3 2 − 3 d Γ 5 and ζ ′ \zeta' ζ ′ as defined in Lemma 17, the final values of A L G ( i + 2 ) , A L G ( i ) \mathrm{ALG}^{(i+2)},\mathrm{ALG}^{(i)} ALG ( i + 2 ) , ALG ( i ) satisfy
Φ ( A L G ( i ) ) − Φ ( A L G ( i + 2 ) ) ≥ [ min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) . (1) \Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}^{(i+2)})\ge
\left[
\min\left\{
\frac{d\Gamma-1}{2d\Gamma},
\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}
\right\}
-\left(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1\right)
\right]\cdot\Phi(\mathrm{ALG}_{\rho}^{(i+1)}\setminus\mathrm{SOL}). \tag*{(1)} Φ ( ALG ( i ) ) − Φ ( ALG ( i + 2 ) ) ≥ [ min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . (1) Proof. We can lower-bound Φ ( A L G ( i + 1 ) ) − Φ ( A L G ρ ( i + 2 ) ) \Phi(\mathrm{ALG}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho}^{(i+2)}) Φ ( ALG ( i + 1 ) ) − Φ ( ALG ρ ( i + 2 ) ) Φ ( A L G ( i + 1 ) ) − Φ ( A L G ( i + 2 ) ) \Phi(\mathrm{ALG}^{(i+1)})-\Phi(\mathrm{ALG}^{(i+2)}) Φ ( ALG ( i + 1 ) ) − Φ ( ALG ( i + 2 ) )
Φ ′ ( A L G ( i + 1 ) ) − Φ ′ ( A L G ρ ( i + 2 ) ) ≤ Φ ′ ( A L G ρ ( i + 1 ) ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( S O L ) . \Phi'(\mathrm{ALG}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho}^{(i+2)})\le\Phi'(\mathrm{ALG}_{\rho}^{(i+1)})\le(d\Gamma'+\kappa+1+\varepsilon)\Phi'(\mathrm{SOL}). Φ ′ ( ALG ( i + 1 ) ) − Φ ′ ( ALG ρ ( i + 2 ) ) ≤ Φ ′ ( ALG ρ ( i + 1 ) ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL ) . because when the loop in Line 10 concludes, we may have a violation of the condition Φ ′ ( A L G ρ ( i + 1 ) ) ≤ ( d Γ ′ + κ ) Φ ′ ( S O L ) \Phi'(\mathrm{ALG}_{\rho}^{(i+1)})\le(d\Gamma'+\kappa)\Phi'(\mathrm{SOL}) Φ ′ ( ALG ρ ( i + 1 ) ) ≤ ( d Γ ′ + κ ) Φ ′ ( SOL ) Φ ′ ( A L G ρ ( i + 1 ) ) \Phi'(\mathrm{ALG}_{\rho}^{(i+1)}) Φ ′ ( ALG ρ ( i + 1 ) ) ( 1 + ε ) Φ ′ ( S O L ) (1+\varepsilon)\Phi'(\mathrm{SOL}) ( 1 + ε ) Φ ′ ( SOL ) ( 1 + ε ) Φ ′ ( S O L ) (1+\varepsilon)\Phi'(\mathrm{SOL}) ( 1 + ε ) Φ ′ ( SOL )
Then we apply Lemma 16 to Φ ( A L G ( i ) ) − Φ ( A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}_{\rho}^{(i+1)}) Φ ( ALG ( i ) ) − Φ ( ALG ρ ( i + 1 ) ) Φ ( A L G ρ ( i + 1 ) ) − Φ ( A L G ρ ( i + 2 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho}^{(i+2)}) Φ ( ALG ρ ( i + 1 ) ) − Φ ( ALG ρ ( i + 2 ) ) T ≤ d Γ ′ + κ + 1 + ε T\le d\Gamma'+\kappa+1+\varepsilon T ≤ d Γ ′ + κ + 1 + ε
Φ ( A L G ( i ) ) − Φ ( A L G ( i + 2 ) ) = [ Φ ( A L G ( i ) ) − Φ ( A L G ρ ( i + 1 ) ) ] + [ Φ ( A L G ρ ( i + 1 ) ) − Φ ( A L G ρ ( i + 2 ) ) ] ≥ [ min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) . \begin{aligned}
\Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}^{(i+2)})
={}&[\Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}_{\rho}^{(i+1)})]+[\Phi(\mathrm{ALG}_{\rho}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho}^{(i+2)})]\\
\ge{}&\left[
\min\left\{
\frac{d\Gamma-1}{2d\Gamma},
\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}
\right\}
-\left(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1\right)
\right]\\
&\cdot\Phi(\mathrm{ALG}_{\rho}^{(i+1)}\setminus\mathrm{SOL}).
\end{aligned} Φ ( ALG ( i ) ) − Φ ( ALG ( i + 2 ) ) = ≥ [ Φ ( ALG ( i ) ) − Φ ( ALG ρ ( i + 1 ) )] + [ Φ ( ALG ρ ( i + 1 ) ) − Φ ( ALG ρ ( i + 2 ) )] [ min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . Finally, the following lemma, whose proof is left to the appendix, concludes about the fact that the DoubleApprox algorithm finds a solution A L G ∗ \mathrm{ALG}^{*} ALG ∗ Φ \Phi Φ Φ ′ \Phi' Φ ′
Lemma 19 (generalizes Lemma 5.17 from [6 ] ). Suppose Γ , Γ ′ , κ \Gamma,\Gamma',\kappa Γ , Γ ′ , κ and ε \varepsilon ε are chosen such that for ζ ′ \zeta' ζ ′ as defined in Lemma 17,
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , \min\left\{
\frac{d\Gamma-1}{2d\Gamma},
\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}
\right\}
-\left(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1\right)>0, min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , and 0 < ε ≤ 2 3 − 5 3 d Γ 0<\varepsilon\le\frac{2}{3}-\frac{5}{3d\Gamma} 0 < ε ≤ 3 2 − 3 d Γ 5 Let η \eta η equal
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) 1 + d Γ d Γ − 1 ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) . \frac{
\min\left\{
\frac{d\Gamma-1}{2d\Gamma},
\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}
\right\}
-\left(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1\right)
}{
1+\frac{d\Gamma}{d\Gamma-1}\left(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1\right)
}. 1 + d Γ − 1 d Γ ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) . Assume η > 0 \eta>0 η > 0 and let I = 2 ( ⌈ log n max i ∈ Ω ϕ ( i ) min i ∈ Ω , ϕ ( i ) > 0 ϕ ( i ) / log ( 1 + η ) ⌉ + 1 ) I=2\left(\left\lceil\log\frac{n\max_{i\in\Omega}\phi(i)}{\min_{i\in\Omega,\ \phi(i)>0}\phi(i)}\big/\log(1+\eta)\right\rceil+1\right) I = 2 ( ⌈ log m i n i ∈ Ω , ϕ ( i ) > 0 ϕ ( i ) n m a x i ∈ Ω ϕ ( i ) / log ( 1 + η ) ⌉ + 1 ) Then there exists some intermediate value A L G ∗ \mathrm{ALG}^{*} ALG ∗ assigned to A L G ρ ( i ) \mathrm{ALG}_{\rho}^{(i)} ALG ρ ( i ) by the DoubleApprox algorithm for some i ≤ I i\le I i ≤ I and ρ \rho ρ such that Φ ( A L G ∗ ∖ S O L ) ≤ d Γ Φ ( S O L ∖ A L G ∗ ) \Phi(\mathrm{ALG}^{*}\setminus\mathrm{SOL})\le d\Gamma\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{*}) Φ ( ALG ∗ ∖ SOL ) ≤ d ΓΦ ( SOL ∖ ALG ∗ ) and Φ ′ ( A L G ∗ ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( S O L ) \Phi'(\mathrm{ALG}^{*})\le(d\Gamma'+\kappa+1+\varepsilon)\Phi'(\mathrm{SOL}) Φ ′ ( ALG ∗ ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL )
These results imply Lemma 15, which provides a very controlled solution on w w w w ′ w' w ′
Now, we get to the last lemma before Theorem 13, which provides an ASO described in Algorithm 4, and implies Theorem 13 through Theorem 2.
Lemma 20 (generalizes Lemma 5.6 of [6 ] ). Fix any Γ ′ > 1 , κ > 0 , ε ∈ ( 0 , 1 / 4 ) \Gamma'>1,\kappa>0,\varepsilon\in(0,1/4) Γ ′ > 1 , κ > 0 , ε ∈ ( 0 , 1/4 ) and let Γ \Gamma Γ be as in Lemma 15. Let α = d Γ Λ ( ⌈ d Γ ′ + κ + 1 + ε ⌉ + 1 ) + 1 \alpha=d\Gamma\Lambda(\lceil d\Gamma'+\kappa+1+\varepsilon\rceil+1)+1 α = d ΓΛ (⌈ d Γ ′ + κ + 1 + ε ⌉ + 1 ) + 1 and β = d Γ \beta=d\Gamma β = d Γ Then, there exists an ( α , β ) (\alpha,\beta) ( α , β ) ASO for the LP formulation of the robust version of P \mathcal{P} P
Data: ( x , r ) (x,r) ( x , r ) P R \mathcal{P}_{R} P R
Check the problem constraints A x ≤ b Ax \le b A x ≤ b
w ‾ ← \overline{w} \leftarrow w ← ∀ i ∈ Ω \forall i \in\Omega ∀ i ∈ Ω w i = u i x i − ℓ i ( x i − 1 ) w_i=u_ix_i-\ell_i(x_i-1) w i = u i x i − ℓ i ( x i − 1 )
w ′ ← w' \leftarrow w ′ ← ∀ i ∈ Ω \forall i \in\Omega ∀ i ∈ Ω w i ′ = ℓ i ( 1 − x i ) w'_i=\ell_i(1-x_i) w i ′ = ℓ i ( 1 − x i )
A L G ← \mathit{ALG} \leftarrow ALG ← w , w ′ w,w' w , w ′
for A L G j ∈ A L G \mathit{ALG}_j \in\mathit{ALG} ALG j ∈ ALG
if ∑ e ∉ A L G j u e x e + ∑ e ∈ A L G j ℓ e ( x e − 1 ) > r \sum_{e\notin\mathit{ALG}_j}u_ex_e+\sum_{e\in\mathit{ALG}_j}\ell_e(x_e-1)>r ∑ e ∈ / ALG j u e x e + ∑ e ∈ ALG j ℓ e ( x e − 1 ) > r
w ‾ ← \overline{w} \leftarrow w ← ∀ i ∈ Ω \forall i\in\Omega ∀ i ∈ Ω w i = { ℓ i if i ∈ A L G j , u i otherwise w_i=\begin{cases}\ell_i & \text{if }i\in\mathit{ALG}_j,\\ u_i & \text{otherwise}\end{cases} w i = { ℓ i u i if i ∈ ALG j , otherwise
return w ‾ ( x ) ≤ w ‾ ( A L G j ) + r \overline{w}(x)\le\overline{w}(\mathit{ALG}_j)+r w ( x ) ≤ w ( ALG j ) + r
return F e a s i b l e \mathit{Feasible} Feasible
Algorithm 4: General-P R \mathcal{P}_{R} P R ( x , r ) (x,r) ( x , r ) Approximate separation oracle for the P R \mathcal{P}_{R} P R
Proof. We show that Algorithm 4 is an ( α , β ) (\alpha,\beta) ( α , β ) P R \mathcal{P}_{R} P R w ∗ w^* w ∗ S O L \mathit{SOL} SOL
∑ e ∈ Ω w e ∗ x e > α ∑ e ∈ S O L w e ∗ + β r , \sum_{e\in\Omega}w_e^*x_e>\alpha\sum_{e\in\mathit{SOL}}w_e^*+\beta r, e ∈ Ω ∑ w e ∗ x e > α e ∈ SOL ∑ w e ∗ + β r , then if A L G i \mathit{ALG}_i ALG i A L G i \mathit{ALG}_i ALG i
Suppose that such w ∗ w^* w ∗ S O L \mathit{SOL} SOL w ‾ \overline{w} w e ∈ Ω e\in\Omega e ∈ Ω w ‾ e = ℓ e \overline{w}_e=\ell_e w e = ℓ e e ∈ S e\in S e ∈ S u e u_e u e
∑ e ∈ Ω w ‾ e x e = ∑ e ∈ S O L ℓ e x e + ∑ e ∉ S O L u e x e > α ∑ e ∈ S O L ℓ e + β r . \sum_{e\in\Omega}\overline{w}_ex_e=\sum_{e\in\mathit{SOL}}\ell_ex_e+\sum_{e\notin\mathit{SOL}}u_ex_e>\alpha\sum_{e\in\mathit{SOL}}\ell_e+\beta r. e ∈ Ω ∑ w e x e = e ∈ SOL ∑ ℓ e x e + e ∈ / SOL ∑ u e x e > α e ∈ SOL ∑ ℓ e + β r . This implies that the regret of x x x S O L \mathit{SOL} SOL ( α − 1 ) ∑ e ∈ S O L ℓ e + β r (\alpha-1)\sum_{e\in\mathit{SOL}}\ell_e+\beta r ( α − 1 ) ∑ e ∈ SOL ℓ e + β r A L G j \mathit{ALG}_j ALG j w w w w e = u e x e + ℓ e ( 1 − x e ) w_e=u_ex_e+\ell_e(1-x_e) w e = u e x e + ℓ e ( 1 − x e ) w ′ w' w ′ w e ′ = ℓ e ( 1 − x e ) w'_e=\ell_e(1-x_e) w e ′ = ℓ e ( 1 − x e ) x x x S O L \mathit{SOL} SOL
∑ e ∉ S O L u e x e − ∑ e ∈ S O L ℓ e ( 1 − x e ) = w ( Ω ∖ S O L ) − ∑ e ∈ Ω ℓ e ( 1 − x e ) . \sum_{e\notin\mathit{SOL}}u_ex_e-\sum_{e\in\mathit{SOL}}\ell_e(1-x_e)=w(\Omega\setminus\mathit{SOL})-\sum_{e\in\Omega}\ell_e(1-x_e). e ∈ / SOL ∑ u e x e − e ∈ SOL ∑ ℓ e ( 1 − x e ) = w ( Ω ∖ SOL ) − e ∈ Ω ∑ ℓ e ( 1 − x e ) . Therefore, with the earlier lower bound on the regret of x x x S O L \mathit{SOL} SOL
w ( Ω ∖ S O L ) − ∑ e ∈ Ω ℓ e ( 1 − x e ) > ( α − 1 ) ∑ e ∈ S O L ℓ e + β r . w(\Omega\setminus\mathit{SOL})-\sum_{e\in\Omega}\ell_e(1-x_e)>(\alpha-1)\sum_{e\in\mathit{SOL}}\ell_e+\beta r. w ( Ω ∖ SOL ) − e ∈ Ω ∑ ℓ e ( 1 − x e ) > ( α − 1 ) e ∈ SOL ∑ ℓ e + β r . Now, we decompose w ( Ω ∖ S O L ) = w ( Ω ∖ ( S O L ∪ A L G j ) ) + w ( A L G j ∖ S O L ) w(\Omega\setminus\mathit{SOL})=w(\Omega\setminus(\mathit{SOL}\cup\mathit{ALG}_j))+w(\mathit{ALG}_j\setminus\mathit{SOL}) w ( Ω ∖ SOL ) = w ( Ω ∖ ( SOL ∪ ALG j )) + w ( ALG j ∖ SOL )
w ( A L G j ∖ S ) > ( α − 1 ) ∑ e ∈ S O L ℓ e + β r − w ( Ω ∖ ( S O L ∪ A L G j ) ) + ∑ e ∈ Ω ℓ e ( 1 − x e ) = ( α − 1 ) ∑ e ∈ S O L ℓ e + β r − ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) u e x e + ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) . \begin{aligned}
w(\mathit{ALG}_j\setminus S)>(\alpha-1)\sum_{e\in\mathit{SOL}}\ell_e+\beta r-w(\Omega\setminus(\mathit{SOL}\cup\mathit{ALG}_j))+\sum_{e\in\Omega}\ell_e(1-x_e) \\
&=(\alpha-1)\sum_{e\in\mathit{SOL}}\ell_e+\beta r-\sum_{e\in\Omega\setminus(\mathit{SOL}\cup\mathit{ALG}_j)}u_ex_e+\sum_{e\in\mathit{SOL}\cup\mathit{ALG}_j}\ell_e(1-x_e).
\end{aligned} w ( ALG j ∖ S ) > ( α − 1 ) e ∈ SOL ∑ ℓ e + β r − w ( Ω ∖ ( SOL ∪ ALG j )) + e ∈ Ω ∑ ℓ e ( 1 − x e ) = ( α − 1 ) e ∈ SOL ∑ ℓ e + β r − e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ u e x e + e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) . Now, the fact that from Lemma 15, w ( A L G j ∖ S O L ) ≤ β w ( S O L ∖ A L G j ) w(\mathit{ALG}_j\setminus\mathit{SOL})\le\beta w(\mathit{SOL}\setminus\mathit{ALG}_j) w ( ALG j ∖ SOL ) ≤ β w ( SOL ∖ ALG j )
w ( S O L ∖ A L G j ) > 1 β [ ( α − 1 ) ∑ e ∈ S O L ℓ e + β r − ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) u e x e + ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) ] . w(\mathit{SOL}\setminus\mathit{ALG}_j)>\frac{1}{\beta}\left[(\alpha-1)\sum_{e\in\mathit{SOL}}\ell_e+\beta r-\sum_{e\in\Omega\setminus(\mathit{SOL}\cup\mathit{ALG}_j)}u_ex_e+\sum_{e\in\mathit{SOL}\cup\mathit{ALG}_j}\ell_e(1-x_e)\right]. w ( SOL ∖ ALG j ) > β 1 ( α − 1 ) e ∈ SOL ∑ ℓ e + β r − e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ u e x e + e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) . We are interested in the regret of the fractional solution x x x A L G j \mathit{ALG}_j ALG j
w ( Ω ∖ A L G j ) − ∑ e ∈ Ω ℓ e ( 1 − x e ) = w ( Ω ∖ ( S O L ∪ A L G j ) ) + w ( S O L ∖ A L G j ) − ∑ e ∈ Ω ℓ e ( 1 − x e ) > ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) ( u e x e + ℓ e ( 1 − x e ) ) + 1 β [ ( α − 1 ) ∑ e ∈ S O L ℓ e + β r − ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) u e x e + ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) ] − ∑ e ∈ Ω ℓ e ( 1 − x e ) = r + β − 1 β ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) u e x e + α − 1 β ∑ e ∈ S O L ℓ e + 1 β ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) − ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) > r + β − 1 β ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) u e x e + α − 1 − β β ∑ e ∈ S O L ℓ e + 1 β ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) − ∑ e ∈ A L G j ∖ S O L ℓ e ( 1 − x e ) . \begin{aligned}
w(\Omega\setminus\mathrm{ALG}_j)-\sum_{e\in\Omega}\ell_e(1-x_e)
&=w(\Omega\setminus(\mathrm{SOL}\cup\mathrm{ALG}_j))+w(\mathrm{SOL}\setminus\mathrm{ALG}_j)-\sum_{e\in\Omega}\ell_e(1-x_e)\\
&>\sum_{e\in\Omega\setminus(\mathrm{SOL}\cup\mathrm{ALG}_j)}(u_ex_e+\ell_e(1-x_e))\\
&\quad+\frac{1}{\beta}\left[(\alpha-1)\sum_{e\in\mathrm{SOL}}\ell_e+\beta r-\sum_{e\in\Omega\setminus(\mathrm{SOL}\cup\mathrm{ALG}_j)}u_ex_e+\sum_{e\in\mathrm{SOL}\cup\mathrm{ALG}_j}\ell_e(1-x_e)\right]-\sum_{e\in\Omega}\ell_e(1-x_e)\\
&=r+\frac{\beta-1}{\beta}\sum_{e\in\Omega\setminus(\mathrm{SOL}\cup\mathrm{ALG}_j)}u_ex_e+\frac{\alpha-1}{\beta}\sum_{e\in\mathrm{SOL}}\ell_e+\frac{1}{\beta}\sum_{e\in\mathrm{SOL}\cup\mathrm{ALG}_j}\ell_e(1-x_e)-\sum_{e\in\mathrm{SOL}\cup\mathrm{ALG}_j}\ell_e(1-x_e)\\
&>r+\frac{\beta-1}{\beta}\sum_{e\in\Omega\setminus(\mathrm{SOL}\cup\mathrm{ALG}_j)}u_ex_e+\frac{\alpha-1-\beta}{\beta}\sum_{e\in\mathrm{SOL}}\ell_e+\frac{1}{\beta}\sum_{e\in\mathrm{SOL}\cup\mathrm{ALG}_j}\ell_e(1-x_e)-\sum_{e\in\mathrm{ALG}_j\setminus\mathrm{SOL}}\ell_e(1-x_e).
\end{aligned} w ( Ω ∖ ALG j ) − e ∈ Ω ∑ ℓ e ( 1 − x e ) = w ( Ω ∖ ( SOL ∪ ALG j )) + w ( SOL ∖ ALG j ) − e ∈ Ω ∑ ℓ e ( 1 − x e ) > e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ ( u e x e + ℓ e ( 1 − x e )) + β 1 ( α − 1 ) e ∈ SOL ∑ ℓ e + β r − e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ u e x e + e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) − e ∈ Ω ∑ ℓ e ( 1 − x e ) = r + β β − 1 e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ u e x e + β α − 1 e ∈ SOL ∑ ℓ e + β 1 e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) − e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) > r + β β − 1 e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ u e x e + β α − 1 − β e ∈ SOL ∑ ℓ e + β 1 e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) − e ∈ ALG j ∖ SOL ∑ ℓ e ( 1 − x e ) . Finally, since α − 1 − β β = Λ ( d Γ ′ + κ + 1 + ε ) \frac{\alpha-1-\beta}{\beta}=\Lambda(d\Gamma^\prime+\kappa+1+\varepsilon) β α − 1 − β = Λ ( d Γ ′ + κ + 1 + ε )
∑ e ∈ A L G j ∖ S O L ℓ e ( 1 − x e ) ≤ α − 1 − β β ∑ e ∈ S ℓ e ( 1 − x e ) ≤ α − 1 − β β ∑ e ∈ S O L ℓ e . \sum_{e\in\mathrm{ALG}_j\setminus\mathrm{SOL}}\ell_e(1-x_e)\leq\frac{\alpha-1-\beta}{\beta}\sum_{e\in S}\ell_e(1-x_e)\leq\frac{\alpha-1-\beta}{\beta}\sum_{e\in\mathrm{SOL}}\ell_e. e ∈ ALG j ∖ SOL ∑ ℓ e ( 1 − x e ) ≤ β α − 1 − β e ∈ S ∑ ℓ e ( 1 − x e ) ≤ β α − 1 − β e ∈ SOL ∑ ℓ e . Therefore, the regret of the fractional solution x x x A L G j \mathrm{ALG}_j ALG j w w w
w ( Ω ∖ A L G j ) − ∑ e ∈ Ω ℓ e ( 1 − x e ) > r + β − 1 β ∑ e ∈ Ω ∖ ( S O L ∪ A L G j ) u e x e + 1 β ∑ e ∈ S O L ∪ A L G j ℓ e ( 1 − x e ) > r . \begin{aligned}
w(\Omega\setminus\mathrm{ALG}_j)-\sum_{e\in\Omega}\ell_e(1-x_e)
&>r+\frac{\beta-1}{\beta}\sum_{e\in\Omega\setminus(\mathrm{SOL}\cup\mathrm{ALG}_j)}u_ex_e+\frac{1}{\beta}\sum_{e\in\mathrm{SOL}\cup\mathrm{ALG}_j}\ell_e(1-x_e)\\
&>r.
\end{aligned} w ( Ω ∖ ALG j ) − e ∈ Ω ∑ ℓ e ( 1 − x e ) > r + β β − 1 e ∈ Ω ∖ ( SOL ∪ ALG j ) ∑ u e x e + β 1 e ∈ SOL ∪ ALG j ∑ ℓ e ( 1 − x e ) > r . This concludes, and shows that the algorithm General-P R \mathcal{P}_R P R
We show in the following § 4.4 that we can always take Γ = Γ ′ = 17 \Gamma=\Gamma^\prime=17 Γ = Γ ′ = 17 κ = d \kappa=d κ = d Theorem 13 .
Simple bounds for Γ \Gamma Γ Γ ′ \Gamma^\prime Γ ′ κ \kappa κ
In order to make the results more practical and comparable, we want to provide some fixed values of Γ \Gamma Γ Γ ′ \Gamma^\prime Γ ′ κ \kappa κ
min { d Γ − 1 2 d Γ ′ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , \min\left\{\frac{d\Gamma-1}{2d\Gamma^\prime},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}-\left(e^{\zeta^\prime(d\Gamma^\prime+\kappa+1+\varepsilon)}-1\right)>0, min { 2 d Γ ′ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , where ζ ′ = d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) \zeta^\prime=\frac{d(1+\varepsilon)\Gamma^\prime}{(\sqrt{\Gamma^\prime}-1)(\sqrt{\Gamma^\prime}-1-\varepsilon)(d\Gamma^\prime-1)(d\Gamma-1)} ζ ′ = ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) d ( 1 + ε ) Γ ′ 0 < ε < 2 3 − 5 3 d Γ 0<\varepsilon<\frac{2}{3}-\frac{5}{3d\Gamma} 0 < ε < 3 2 − 3 d Γ 5 ε = 1 5 \varepsilon=\frac{1}{5} ε = 5 1 Γ ≥ 4 \Gamma\geq4 Γ ≥ 4
min { d Γ − 1 2 d Γ ′ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 6 5 ) κ d 2 6 5 Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 6 5 ) − 1 ) > 0 , \min\left\{\frac{d\Gamma-1}{2d\Gamma^\prime},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-\frac{6}{5})\kappa}{d^2\frac{6}{5}\Gamma^2}\right\}-\left(e^{\zeta^\prime(d\Gamma^\prime+\kappa+\frac{6}{5})}-1\right)>0, min { 2 d Γ ′ d Γ − 1 , d 2 5 6 Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 5 6 ) κ } − ( e ζ ′ ( d Γ ′ + κ + 5 6 ) − 1 ) > 0 , with:
ζ ′ = d 6 5 Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 6 5 ) ( d Γ ′ − 1 ) ( d Γ − 1 ) . \zeta^\prime=\frac{d\frac{6}{5}\Gamma^\prime}{(\sqrt{\Gamma^\prime}-1)(\sqrt{\Gamma^\prime}-\frac{6}{5})(d\Gamma^\prime-1)(d\Gamma-1)}. ζ ′ = ( Γ ′ − 1 ) ( Γ ′ − 5 6 ) ( d Γ ′ − 1 ) ( d Γ − 1 ) d 5 6 Γ ′ . In order to minimize max ( Γ , Γ ′ ) \max(\Gamma,\Gamma^\prime) max ( Γ , Γ ′ ) Γ = Γ ′ \Gamma=\Gamma^\prime Γ = Γ ′ κ = d \kappa=d κ = d Γ \Gamma Γ Γ ′ \Gamma^\prime Γ ′ κ \kappa κ d d d d d d d = 1 d=1 d = 1 Γ = Γ ′ \Gamma=\Gamma^\prime Γ = Γ ′ Γ = Γ ′ = 17 \Gamma=\Gamma^\prime=17 Γ = Γ ′ = 17 κ = d \kappa=d κ = d
Application to Weighted k k k
In this section, we will show that the local search-based H k H_k H k k k k [7 ] can be modified slightly to satisfy the prerequisites, and therefore that the Weighted k k k Ω \Omega Ω Ω ‾ = { A ∣ B ∈ Ω , A ⊆ B } \overline{\Omega} = \{A \mid B \in\Omega, A \subseteq B\} Ω = { A ∣ B ∈ Ω , A ⊆ B } s ∈ Ω ‾ ∖ Ω s \in\overline{\Omega} \setminus\Omega s ∈ Ω ∖ Ω Ω \Omega Ω Ω \Omega Ω Ω ‾ ∖ Ω \overline{\Omega} \setminus\Omega Ω ∖ Ω Ω ‾ \overline{\Omega} Ω Ω \Omega Ω [ ℓ , u ] [\ell,u] [ ℓ , u ] s ∈ Ω ‾ ∖ Ω s \in\overline{\Omega} \setminus\Omega s ∈ Ω ∖ Ω ℓ \ell ℓ u u u Ω ‾ \overline{\Omega} Ω Ω \Omega Ω u u u ℓ \ell ℓ
In order to avoid this problem, we will rewrite the local search algorithm slightly by always working on Ω \Omega Ω Ω ‾ \overline{\Omega} Ω ( S , D ) (S,D) ( S , D ) S ⊆ Ω S \subseteq\Omega S ⊆ Ω D D D S S S Ω ‾ \overline{\Omega} Ω { D s ∣ s ∈ S } \{D_s \mid s \in S\} { D s ∣ s ∈ S } ⋃ Ω \bigcup\Omega ⋃ Ω
An instance is a set Ω \Omega Ω w : Ω → R + w : \Omega\to\mathbb{R}_+ w : Ω → R + Φ \Phi Φ ( S , D ) (S,D) ( S , D )
Φ ( S ) = ∑ s ∈ S H ∣ D ( s ) ∣ w s , \Phi(S) = \sum_{s \in S} H_{\lvert D(s)\rvert} w_s, Φ ( S ) = s ∈ S ∑ H ∣ D ( s )∣ w s , where we recall that H k H_k H k k k k ∑ i = 1 k 1 i \sum_{i=1}^{k} \frac{1}{i} ∑ i = 1 k i 1 ( S 0 , D 0 ) (S_0,D_0) ( S 0 , D 0 ) S 0 S_0 S 0 D 0 D_0 D 0 x ∈ ⋃ Ω x \in\bigcup\Omega x ∈ ⋃ Ω s x ∈ S 0 s_x \in S_0 s x ∈ S 0 x ∈ s x x \in s_x x ∈ s x D 0 : s ∈ S 0 ↦ { x ∣ s x = s } D_0 : s \in S_0 \mapsto\{x \mid s_x = s\} D 0 : s ∈ S 0 ↦ { x ∣ s x = s }
Now, we are ready to describe the moves of the algorithm. When the algorithm is at a solution state ( S i , D i ) (S_i,D_i) ( S i , D i ) Z ⊆ Ω ‾ Z \subseteq\overline{\Omega} Z ⊆ Ω k k k Z Z Z ( S i , D i ) (S_i,D_i) ( S i , D i ) ( S i ′ , D i ′ ) (S'_i,D'_i) ( S i ′ , D i ′ ) s ′ ∈ Z s' \in Z s ′ ∈ Z t s ′ ∈ Ω t_{s'} \in\Omega t s ′ ∈ Ω s ′ s' s ′ Ω \Omega Ω
S i ′ = { t s ′ ∣ s ′ ∈ Z } ∪ { s ∣ s ∈ S i , D s ⊈ ⋃ s ′ ∈ Z s ′ } . S'_i = \{t_{s'} \mid s' \in Z\} \cup\left\{s \mid s \in S_i, D_s \nsubseteq\bigcup_{s' \in Z} s'\right\}. S i ′ = { t s ′ ∣ s ′ ∈ Z } ∪ { s ∣ s ∈ S i , D s ⊈ s ′ ∈ Z ⋃ s ′ } . Then, for each s ′ ∈ Z s' \in Z s ′ ∈ Z D i ′ ( t s ′ ) = s ′ D'_i(t_{s'}) = s' D i ′ ( t s ′ ) = s ′ D i ′ ( s ) = D i ( s ) D'_i(s) = D_i(s) D i ′ ( s ) = D i ( s ) s ∈ S i ′ s \in S'_i s ∈ S i ′ S i ′ = A Z ( S i , D i ) S'_i = A_Z(S_i,D_i) S i ′ = A Z ( S i , D i ) D i ′ = B Z ( S i , D i ) D'_i = B_Z(S_i,D_i) D i ′ = B Z ( S i , D i ) ( S i ′ , D i ′ ) (S'_i,D'_i) ( S i ′ , D i ′ ) Z Z Z
Therefore, the set of moves available in a solution state ( S i , D i ) (S_i,D_i) ( S i , D i )
Π ( S i , D i ) = { ( A Z ( S i , D i ) , B Z ( S i , D i ) ) ∣ Z ⊆ Ω ‾ , ∣ Z ∣ ≤ k , ∀ a , b ∈ Z , a ∩ b = ∅ } . \Pi_{(S_i,D_i)} = \left\{(A_Z(S_i,D_i), B_Z(S_i,D_i)) \mid Z \subseteq\overline{\Omega}, \lvert Z\rvert\leq k, \ \forall a,b \in Z, a \cap b = \varnothing\right\}. Π ( S i , D i ) = { ( A Z ( S i , D i ) , B Z ( S i , D i )) ∣ Z ⊆ Ω , ∣ Z ∣ ≤ k , ∀ a , b ∈ Z , a ∩ b = ∅ } . Remark that this set has size at most ( ∣ Ω ‾ ∣ k ) ≤ ( 2 k n ) k = O ( n k ) \binom{\lvert\overline{\Omega}\rvert}{k} \leq(2^k n)^k = O(n^k) ( k ∣ Ω ∣ ) ≤ ( 2 k n ) k = O ( n k ) ( S i , D i ) (S_i,D_i) ( S i , D i ) ( S i + 1 , D i + 1 ) ∈ Π ( S i , D i ) (S_{i+1},D_{i+1}) \in\Pi_{(S_i,D_i)} ( S i + 1 , D i + 1 ) ∈ Π ( S i , D i ) Φ ( S i + 1 , D i + 1 ) ≤ Φ ( S i , D i ) \Phi(S_{i+1},D_{i+1}) \leq\Phi(S_i,D_i) Φ ( S i + 1 , D i + 1 ) ≤ Φ ( S i , D i ) Φ \Phi Φ
The proof that every local optimum is an H k H_k H k [7 ] still stands here, since we only add possible moves. Furthermore, we have the added benefit that the algorithm maintains at all times a solution on Ω \Omega Ω { D i ( s ) ∣ s ∈ S i } ⊆ Ω ‾ \{D_i(s) \mid s \in S_i\} \subseteq\overline{\Omega} { D i ( s ) ∣ s ∈ S i } ⊆ Ω [7 ] shows has the approximation guarantee.
Well-behaved potential. Given a weight function w w w Ω \Omega Ω ( S , D ) (S,D) ( S , D ) Φ ( S , D ) = ∑ s ∈ S w ( s ) H ∣ s ∣ \Phi(S,D) = \sum_{s \in S} w(s)H_{\lvert s\rvert} Φ ( S , D ) = ∑ s ∈ S w ( s ) H ∣ s ∣ s ∈ Ω s \in\Omega s ∈ Ω ϕ ( s ) = w ( s ) H ∣ s ∣ \phi(s) = w(s)H_{|s|} ϕ ( s ) = w ( s ) H ∣ s ∣ Φ ( S , D ) = ∑ s ∈ S ϕ ( s ) \Phi(S,D) = \sum_{s \in S}\phi(s) Φ ( S , D ) = ∑ s ∈ S ϕ ( s ) S S S w ( S ) ≤ Φ ( S ) ≤ H k w ( S ) w(S) \le\Phi(S) \le H_k w(S) w ( S ) ≤ Φ ( S ) ≤ H k w ( S ) Λ 1 = 1 , Λ 2 = H k \Lambda_1 = 1, \Lambda_2 = H_k Λ 1 = 1 , Λ 2 = H k
Minimal Move Covering
Let us fix two solution states ( S , D ) (S,D) ( S , D ) ( T , E ) (T,E) ( T , E )
Π ( S , D ) ( T , E ) = { ( S ′ , D ′ ) ∣ ( S ′ , D ′ ) ∈ Π ( S , D ) , ∅ ⊊ S ′ ∖ S ⊆ T } \Pi_{(S,D)}^{(T,E)} = \{(S',D') \mid(S',D') \in\Pi_{(S,D)}, \varnothing\subsetneq S' \setminus S \subseteq T\} Π ( S , D ) ( T , E ) = {( S ′ , D ′ ) ∣ ( S ′ , D ′ ) ∈ Π ( S , D ) , ∅ ⊊ S ′ ∖ S ⊆ T } contains only moves ( S ′ , D ′ ) (S',D') ( S ′ , D ′ ) S ′ ∖ S S' \setminus S S ′ ∖ S k k k T ∖ S T \setminus S T ∖ S ∣ S ′ ∖ S ∣ ≤ k |S' \setminus S| \le k ∣ S ′ ∖ S ∣ ≤ k S ′ ⊆ Ω S' \subseteq\Omega S ′ ⊆ Ω ∣ S ′ ∣ ≤ k |S'| \le k ∣ S ′ ∣ ≤ k T ∖ S T \setminus S T ∖ S
We define α \alpha α Π ( S , D ) ( T , E ) \Pi_{(S,D)}^{(T,E)} Π ( S , D ) ( T , E ) s ∈ S ∖ T s \in S \setminus T s ∈ S ∖ T E s ⊆ T E_s \subseteq T E s ⊆ T D ( s ) D(s) D ( s ) ∣ D ( s ) ∣ ≤ k |D(s)| \le k ∣ D ( s ) ∣ ≤ k E s E_s E s k k k ( S ′ , D ′ ) (S',D') ( S ′ , D ′ ) E s E_s E s Π ( S , D ) ( T , E ) \Pi_{(S,D)}^{(T,E)} Π ( S , D ) ( T , E ) S ′ ∖ S = E s ⊆ T S' \setminus S = E_s \subseteq T S ′ ∖ S = E s ⊆ T α ( S ′ , D ′ ) = 1 \alpha(S',D') = 1 α ( S ′ , D ′ ) = 1 s ∉ S ′ s \notin S' s ∈ / S ′ α \alpha α ∣ S ∖ T ∣ |S \setminus T| ∣ S ∖ T ∣ α \alpha α
First, let s ∈ S ∖ T s \in S \setminus T s ∈ S ∖ T
∑ ( S ′ , D ′ ) ∈ Π ( S , D ) ( T , E ) s ∉ S ′ α ( S ′ , D ′ ) \sum_{\substack{(S',D') \in\Pi_{(S,D)}^{(T,E)} \\ s \notin S'}} \alpha(S',D') ( S ′ , D ′ ) ∈ Π ( S , D ) ( T , E ) s ∈ / S ′ ∑ α ( S ′ , D ′ ) contains at least the move generated by E s E_s E s α \alpha α
Now, let s ′ ∈ T ∖ S s' \in T \setminus S s ′ ∈ T ∖ S
∑ ( S ′ , D ′ ) ∈ Π ( S , D ) ( T , E ) s ′ ∈ S ′ ∖ S α ( S ′ , D ′ ) . \sum_{\substack{(S',D') \in\Pi_{(S,D)}^{(T,E)} \\ s' \in S' \setminus S}} \alpha(S',D'). ( S ′ , D ′ ) ∈ Π ( S , D ) ( T , E ) s ′ ∈ S ′ ∖ S ∑ α ( S ′ , D ′ ) . To do so, remark that this is equivalent to counting how many sets s ∈ S ∖ T s \in S \setminus T s ∈ S ∖ T s ′ ∈ E s s' \in E_s s ′ ∈ E s { D ( s ) ∣ s ∈ S ∖ T } \{D(s) \mid s \in S \setminus T\} { D ( s ) ∣ s ∈ S ∖ T } s ′ ∈ S ′ ∖ S s' \in S' \setminus S s ′ ∈ S ′ ∖ S k k k D ( s ) D(s) D ( s ) k k k
∑ ( S ′ , D ′ ) ∈ Π ( S , D ) ( T , E ) s ′ ∈ S ′ ∖ S α ( S ′ , D ′ ) ≤ k \sum_{\substack{(S',D') \in\Pi_{(S,D)}^{(T,E)} \\ s' \in S' \setminus S}} \alpha(S',D') \le k ( S ′ , D ′ ) ∈ Π ( S , D ) ( T , E ) s ′ ∈ S ′ ∖ S ∑ α ( S ′ , D ′ ) ≤ k Finally, remark that the total mass of α \alpha α ∣ S ∖ T ∣ ≤ n |S \setminus T| \le n ∣ S ∖ T ∣ ≤ n α \alpha α k k k
Efficient Good Move Retrieval
Finally, we show that the efficient good move retrieval property is satisfied (in the following, we omit the second half a solution state for legibility, and keep only the set cover in Ω \Omega Ω
Lemma 21. Given two potentials Φ \Phi Φ Φ ′ \Phi' Φ ′ S S S W ′ > 0 W' > 0 W ′ > 0 S ′ ∈ Π S S' \in\Pi_S S ′ ∈ Π S Φ ( S ′ ∖ S ) − Φ ( S ∖ S ′ ) ≤ W \Phi(S' \setminus S) - \Phi(S \setminus S') \le W Φ ( S ′ ∖ S ) − Φ ( S ∖ S ′ ) ≤ W Φ ′ ( S ′ ∖ S ) − Φ ′ ( S ∖ S ′ ) ≤ W ′ \Phi'(S' \setminus S) - \Phi'(S \setminus S') \le W' Φ ′ ( S ′ ∖ S ) − Φ ′ ( S ∖ S ′ ) ≤ W ′ S ′ ′ S'' S ′′
Proof. Since ∣ Π S ∣ ≤ ( n 2 k ) ≤ 2 k 2 n k = O ( n k ) |\Pi_S| \le\binom{n^2}{k} \le2^{k^2}n^k = O(n^k) ∣ Π S ∣ ≤ ( k n 2 ) ≤ 2 k 2 n k = O ( n k ) k k k S ′ ′ ∈ Π S S'' \in\Pi_S S ′′ ∈ Π S S ′ S' S ′
Robust approximation algorithm. From the prerequisites, Theorem 13 implies the following result as the standard LP relaxation has integrality gap at most H k H_k H k H k H_k H k [7 ] :
Theorem 22. The Weighted k k k ( O ( H k 4 k 2 ) , O ( H k 3 k ) ) (O(H_k^4 k^2), O(H_k^3 k)) ( O ( H k 4 k 2 ) , O ( H k 3 k ))
Conclusion
In this paper, we have developed some proofs found in the first paper about robust approximation algorithms for NP-hard problems [6 ] . We believe that there are still many questions left to be answered. We currently do not know of NP-hard problems that admit an approximation algorithm but no robust approximation algorithm. Showing either that they exist, or that there is a way to transform any approximation algorithm to a robust approximation algorithm would be a big step toward understanding how robust approximation behaves.
A major obstacle to this is that the robust approximation setting is less general that it seems at first glance. Indeed, it only works on problems that admit an approximation algorithm in the non-metric case (since the weights vary independently) and such that the weight is not involved in the feasibility constraints (this disqualifies some scheduling problems, for instance). Similarly, our more general robust approximation theorem (Theorem 13 ) is difficult to apply because these constraints on the kind of problem that can be studied in this robust approximation framework are limiting, and local search with approximation guarantees are somewhat rare when we cannot assume that we work on a metric.
However, in light of the question of knowing whether any approximation algorithm can be turned to a robust approximation algorithm, it seems that we are simply lacking some important tools to release some of the assumptions that we currently need, and some more interesting work needs to be done before the question can be fully solved.
Proof of lem:55 and necessary lemmas
Lemma 16 (Forward Phase Analysis, generalizes Lemma 5.14 of [6 ] ). For any even i i i
ρ = ( 1 + ε ) ⌈ log 1 + ε ( Φ ( ALG ( i ) ∖ SOL ) min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) ) ⌉ min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) \rho=(1+\varepsilon)\left\lceil\log_{1+\varepsilon}\left(\frac{\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})}{\min_{\substack{i\in\Omega\\\phi(i)>0}}\phi(i)}\right)\right\rceil\min_{\substack{i\in\Omega\\\phi(i)>0}}\phi(i) ρ = ( 1 + ε ) log 1 + ε min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) Φ ( ALG ( i ) ∖ SOL ) i ∈ Ω ϕ ( i ) > 0 min ϕ ( i ) *be such that ρ ∈ [ Φ ( ALG ( i ) ∖ SOL ) , ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL ) ] \rho\in[\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL}),(1+\varepsilon)\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})] ρ ∈ [ Φ ( ALG ( i ) ∖ SOL ) , ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL )] ALG ρ ( i + 1 ) \operatorname{ALG}^{(i+1)}_{\rho} ALG ρ ( i + 1 ) ALG ( i ) \operatorname{ALG}^{(i)} ALG ( i ) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) \Phi(\operatorname{ALG}^{(i+1)}_{\rho}\setminus\operatorname{SOL})>d\Gamma\cdot\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i+1)}_{\rho}) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) Φ ( ALG ( i ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ( i ) ) \Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})>d\Gamma\cdot\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)}) Φ ( ALG ( i ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ( i ) ) 0 < ε < 2 / 3 − 5 3 d Γ 0<\varepsilon<2/3-\frac{5}{3d\Gamma} 0 < ε < 2/3 − 3 d Γ 5 ALG ( i ) \operatorname{ALG}^{(i)} ALG ( i ) ALG ρ ( i + 1 ) \operatorname{ALG}^{(i+1)}_{\rho} ALG ρ ( i + 1 )
Φ ( ALG ( i ) ) − Φ ( ALG ρ ( i + 1 ) ) ≥ min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . \Phi(\operatorname{ALG}^{(i)})-\Phi(\operatorname{ALG}^{(i+1)}_{\rho})\geq\min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}\right\}\cdot\Phi(\operatorname{ALG}^{(i+1)}_{\rho}\setminus\operatorname{SOL}). Φ ( ALG ( i ) ) − Φ ( ALG ρ ( i + 1 ) ) ≥ min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . Proof. We analyze one forward phase of the DoubleApprox algorithm. We let ALG ρ , j ( i + 1 ) \operatorname{ALG}^{(i+1)}_{\rho,j} ALG ρ , j ( i + 1 ) ALG ρ ( i + 1 ) \operatorname{ALG}^{(i+1)}_{\rho} ALG ρ ( i + 1 ) j j j J J J ALG ( i ) \operatorname{ALG}^{(i)} ALG ( i ) ALG ρ , 0 ( i + 1 ) \operatorname{ALG}^{(i+1)}_{\rho,0} ALG ρ , 0 ( i + 1 ) ρ ≤ ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL ) \rho\leq(1+\varepsilon)\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL}) ρ ≤ ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL )
Φ ( ALG ρ ( i + 1 ) ) > Φ ( ALG ( i ) ) − ρ / 2 ≥ Φ ( ALG ( i ) ) − 1 + ε 2 Φ ( ALG ( i ) ∖ SOL ) . \Phi(\operatorname{ALG}^{(i+1)}_{\rho})>\Phi(\operatorname{ALG}^{(i)})-\rho/2\geq\Phi(\operatorname{ALG}^{(i)})-\frac{1+\varepsilon}{2}\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL}). Φ ( ALG ρ ( i + 1 ) ) > Φ ( ALG ( i ) ) − ρ /2 ≥ Φ ( ALG ( i ) ) − 2 1 + ε Φ ( ALG ( i ) ∖ SOL ) . Then, by Lemma 7 and the assumption that Φ ( ALG ( i ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ( i ) ) \Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})>d\Gamma\cdot\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)}) Φ ( ALG ( i ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ( i ) )
Φ ( ALG ρ ( i + 1 ) ∖ SOL ) ≥ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) ) = Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) + Φ ( ALG ρ ( i + 1 ) ) − Φ ( ALG ( i ) ) (Lemma 7) ≥ Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) − 1 + ε 2 Φ ( ALG ( i ) ∖ SOL ) ≥ ( 1 − ε 2 − 1 d Γ ) Φ ( ALG ( i ) ∖ SOL ) ≥ 1 10 ρ (since ε ≤ 2 3 − 5 3 d Γ ) . \begin{aligned}
\Phi(\operatorname{ALG}^{(i+1)}_{\rho}\setminus\operatorname{SOL})&\geq\Phi(\operatorname{ALG}^{(i+1)}_{\rho}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i+1)}_{\rho})\\
&=\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)})+\Phi(\operatorname{ALG}^{(i+1)}_{\rho})-\Phi(\operatorname{ALG}^{(i)})\quad\text{(Lemma 7)}\\
&\geq\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)})-\frac{1+\varepsilon}{2}\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})\\
&\geq\left(\frac{1-\varepsilon}{2}-\frac{1}{d\Gamma}\right)\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})\\
&\geq\frac{1}{10}\rho\quad\text{(since }\varepsilon\leq\frac{2}{3}-\frac{5}{3d\Gamma}\text{)}.
\end{aligned} Φ ( ALG ρ ( i + 1 ) ∖ SOL ) ≥ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) ) = Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) + Φ ( ALG ρ ( i + 1 ) ) − Φ ( ALG ( i ) ) (Lemma 7) ≥ Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) − 2 1 + ε Φ ( ALG ( i ) ∖ SOL ) ≥ ( 2 1 − ε − d Γ 1 ) Φ ( ALG ( i ) ∖ SOL ) ≥ 10 1 ρ (since ε ≤ 3 2 − 3 d Γ 5 ) . Because of the assumption that Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) \Phi(\operatorname{ALG}^{(i+1)}_{\rho}\setminus\operatorname{SOL})>d\Gamma\cdot\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i+1)}_{\rho}) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) 1 n 2 Φ ( ALG ρ ( i + 1 ) ∖ SOL ) ≥ 1 10 n 2 ρ \frac{1}{n^{2}}\Phi(\operatorname{ALG}^{(i+1)}_{\rho}\setminus\operatorname{SOL})\geq\frac{1}{10n^{2}}\rho n 2 1 Φ ( ALG ρ ( i + 1 ) ∖ SOL ) ≥ 10 n 2 1 ρ s t o p stop s t o p 1 10 n 2 ρ > 0 \frac{1}{10n^{2}}\rho>0 10 n 2 1 ρ > 0
Now, suppose ALG ρ , J ( i + 1 ) \operatorname{ALG}^{(i+1)}_{\rho,J} ALG ρ , J ( i + 1 ) Φ ( ALG ρ , J ( i + 1 ) ) ≤ Φ ( ALG ( i ) ) − ρ / 2 \Phi(\operatorname{ALG}^{(i+1)}_{\rho,J})\leq\Phi(\operatorname{ALG}^{(i)})-\rho/2 Φ ( ALG ρ , J ( i + 1 ) ) ≤ Φ ( ALG ( i ) ) − ρ /2
Φ ( ALG ( i ) ) − Φ ( ALG ρ , J ( i + 1 ) ) ≥ ρ / 2 ≥ 1 2 Φ ( ALG ( i ) ∖ SOL ) ≥ 1 2 [ Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) ] = 1 2 [ Φ ( ALG ρ , 0 ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , 0 ( i + 1 ) ) ] ≥ 1 2 [ Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , J ( i + 1 ) ) ] ≥ d Γ − 1 2 d Γ Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) . \begin{aligned}
\Phi(\operatorname{ALG}^{(i)})-\Phi(\operatorname{ALG}^{(i+1)}_{\rho,J})&\geq\rho/2\geq\frac{1}{2}\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})\\
&\geq\frac{1}{2}\left[\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)})\right]\\
&=\frac{1}{2}\left[\Phi(\operatorname{ALG}^{(i+1)}_{\rho,0}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i+1)}_{\rho,0})\right]\\
&\geq\frac{1}{2}\left[\Phi(\operatorname{ALG}^{(i+1)}_{\rho,J}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i+1)}_{\rho,J})\right]\\
&\geq\frac{d\Gamma-1}{2d\Gamma}\Phi(\operatorname{ALG}^{(i+1)}_{\rho,J}\setminus\operatorname{SOL}).
\end{aligned} Φ ( ALG ( i ) ) − Φ ( ALG ρ , J ( i + 1 ) ) ≥ ρ /2 ≥ 2 1 Φ ( ALG ( i ) ∖ SOL ) ≥ 2 1 [ Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) ] = 2 1 [ Φ ( ALG ρ , 0 ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , 0 ( i + 1 ) ) ] ≥ 2 1 [ Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , J ( i + 1 ) ) ] ≥ 2 d Γ d Γ − 1 Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) . The second-to-last inequality uses Lemma 7, which implies Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus\mathrm{SOL})-\Phi(\mathrm{SOL} \setminus\mathrm{ALG}_{\rho}^{(i+1)}) Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) ) Φ ( A L G ρ ( i + 1 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+1)} \setminus\mathrm{SOL}) > d\Gamma\cdot\Phi(\mathrm{SOL} \setminus\mathrm{ALG}_{\rho}^{(i+1)}) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) Φ ( A L G ρ , J ( i + 1 ) ) ≤ Φ ( A L G ( i ) ) − ρ / 2 \Phi(\mathrm{ALG}_{\rho,J}^{(i+1)}) \le\Phi(\mathrm{ALG}^{(i)})-\rho/2 Φ ( ALG ρ , J ( i + 1 ) ) ≤ Φ ( ALG ( i ) ) − ρ /2
Now, the loop might otherwise end with Φ ( A L G ρ , J ( i + 1 ) ) > Φ ( A L G ( i ) ) − ρ / 2 \Phi(\mathrm{ALG}_{\rho,J}^{(i+1)}) > \Phi(\mathrm{ALG}^{(i)})-\rho/2 Φ ( ALG ρ , J ( i + 1 ) ) > Φ ( ALG ( i ) ) − ρ /2 Φ ′ ( A L G ρ , J ( i + 1 ) ) > ( d Γ ′ + κ ) χ ′ \Phi'(\mathrm{ALG}_{\rho,J}^{(i+1)}) > (d\Gamma' + \kappa)\chi' Φ ′ ( ALG ρ , J ( i + 1 ) ) > ( d Γ ′ + κ ) χ ′
Φ ( A L G ρ , 0 ( i + 1 ) ) − Φ ( A L G ρ , J ( i + 1 ) ) = ∑ j = 0 J − 1 [ Φ ( A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j + 1 ( i + 1 ) ) ] . \Phi(\mathrm{ALG}_{\rho,0}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,J}^{(i+1)})=\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+1)})\right]. Φ ( ALG ρ , 0 ( i + 1 ) ) − Φ ( ALG ρ , J ( i + 1 ) ) = j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j + 1 ( i + 1 ) ) ] . We bound each Φ ( A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j + 1 ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+1)}) Φ ( ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j + 1 ( i + 1 ) ) Φ ( A L G ρ ( i + 1 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+1)} \setminus\mathrm{SOL}) > d\Gamma\cdot\Phi(\mathrm{SOL} \setminus\mathrm{ALG}_{\rho}^{(i+1)}) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) S ∈ Π A L G ρ , j ( i + 1 ) S O L S \in\Pi_{\mathrm{ALG}_{\rho,j}^{(i+1)}}^{\mathrm{SOL}} S ∈ Π ALG ρ , j ( i + 1 ) SOL
( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ) Φ ( A L G ρ , j ( i + 1 ) ∖ S ) − ( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 1 ) ) ≤ d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) Φ ′ ( S O L ∖ A L G ρ , j ( i + 1 ) ) Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) . \frac{(1+\varepsilon)\Phi'(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S)}{\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S)-(1+\varepsilon)\Phi(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})}
\le
\frac{d(1+\varepsilon)\Gamma}{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}
\frac{\Phi'(\mathrm{SOL} \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})}{\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus\mathrm{SOL})}. Φ ( ALG ρ , j ( i + 1 ) ∖ S ) − ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 1 ) ) ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ) ≤ ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) Φ ′ ( SOL ∖ ALG ρ , j ( i + 1 ) ) . where Φ ( A L G ρ , j ( i + 1 ) ∖ S ) − ( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 1 ) ) > 0 \Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S)-(1+\varepsilon)\Phi(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)}) > 0 Φ ( ALG ρ , j ( i + 1 ) ∖ S ) − ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 1 ) ) > 0
When G R E E D Y S W A P \mathrm{GREEDYSWAP} GREEDYSWAP W W W 1 + ε \sqrt{1+\varepsilon} 1 + ε Φ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j ( i + 1 ) ∖ S ) \Phi(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S) Φ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j ( i + 1 ) ∖ S ) W ′ W' W ′ 1 + ε \sqrt{1+\varepsilon} 1 + ε Φ ′ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ) \Phi'(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S) Φ ′ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ) 1 + ε − 1 > 0 \sqrt{1+\varepsilon}-1>0 1 + ε − 1 > 0 ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) 1 + ε \sqrt{1+\varepsilon} 1 + ε S ′ ∈ Π A L G ρ , j ( i + 1 ) S O L S' \in\Pi_{\mathrm{ALG}_{\rho,j}^{(i+1)}}^{\mathrm{SOL}} S ′ ∈ Π ALG ρ , j ( i + 1 ) SOL
Φ ′ ( S ′ ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ) \Phi'(S' \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S') \le(1+\varepsilon)\Phi'(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S) Φ ′ ( S ′ ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S )
Φ ( S ′ ∖ A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j ( i + 1 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j ( i + 1 ) ∖ S ) \Phi(S' \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S') \le(1+\varepsilon)\Phi(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S) Φ ( S ′ ∖ ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j ( i + 1 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j ( i + 1 ) ∖ S )
Therefore, the move S ∗ ∈ Π A L G ρ , j ( i + 1 ) S O L S^* \in\Pi_{\mathrm{ALG}_{\rho,j}^{(i+1)}}^{\mathrm{SOL}} S ∗ ∈ Π ALG ρ , j ( i + 1 ) SOL ( j + 1 ) (j+1) ( j + 1 ) G R E E D Y S W A P \mathrm{GREEDYSWAP} GREEDYSWAP
Φ ′ ( S ∗ ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ∗ ) Φ ( A L G ρ , j ( i + 1 ) ∖ S ∗ ) − Φ ( S ∗ ∖ A L G ρ , j ( i + 1 ) ) ≤ Φ ′ ( S ′ ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ′ ) Φ ( A L G ρ , j ( i + 1 ) ∖ S ′ ) − Φ ( S ′ ∖ A L G ρ , j ( i + 1 ) ) ≤ ( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ) Φ ( A L G ρ , j ( i + 1 ) ∖ S ) − ( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 1 ) ) ≤ d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) Φ ′ ( S O L ∖ A L G ρ , j ( i + 1 ) ) Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) . \begin{aligned}
\frac{\Phi'(S^* \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S^*)}{\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S^*)-\Phi(S^* \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})}
\le
\frac{\Phi'(S' \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S')}{\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S')-\Phi(S' \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})} \\
&\le
\frac{(1+\varepsilon)\Phi'(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S)}{\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S)-(1+\varepsilon)\Phi(S \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})} \\
&\le
\frac{d(1+\varepsilon)\Gamma}{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}
\frac{\Phi'(\mathrm{SOL} \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})}{\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus\mathrm{SOL})}.
\end{aligned} Φ ( ALG ρ , j ( i + 1 ) ∖ S ∗ ) − Φ ( S ∗ ∖ ALG ρ , j ( i + 1 ) ) Φ ′ ( S ∗ ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ∗ ) ≤ Φ ( ALG ρ , j ( i + 1 ) ∖ S ′ ) − Φ ( S ′ ∖ ALG ρ , j ( i + 1 ) ) Φ ′ ( S ′ ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ′ ) ≤ Φ ( ALG ρ , j ( i + 1 ) ∖ S ) − ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 1 ) ) ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ) ≤ ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) Φ ′ ( SOL ∖ ALG ρ , j ( i + 1 ) ) . Rearranging terms and observing that Φ ′ ( S O L ) ≥ Φ ′ ( S O L ∖ A L G ρ , j ( i + 1 ) ) \Phi'(\mathrm{SOL}) \ge\Phi'(\mathrm{SOL} \setminus\mathrm{ALG}_{\rho,j}^{(i+1)}) Φ ′ ( SOL ) ≥ Φ ′ ( SOL ∖ ALG ρ , j ( i + 1 ) )
Φ ( A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j + 1 ( i + 1 ) ) = Φ ( A L G ρ , j ( i + 1 ) ∖ S ∗ ) − Φ ( S ∗ ∖ A L G ρ , j ( i + 1 ) ) ≥ ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ ⋅ Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) ⋅ Φ ′ ( S ∗ ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ∗ ) Φ ′ ( S O L ) = ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ ⋅ Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) ⋅ Φ ′ ( A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j + 1 ( i + 1 ) ) Φ ′ ( S O L ) . \begin{aligned}
\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+1)})
&=\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S^*)-\Phi(S^* \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})\\
&\ge\frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d(1+\varepsilon)\Gamma}\cdot\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus\mathrm{SOL})\\
&\qquad\cdot\frac{\Phi'(S^* \setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus S^*)}{\Phi'(\mathrm{SOL})}\\
&= \frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d(1+\varepsilon)\Gamma}\cdot\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)} \setminus\mathrm{SOL})\\
&\qquad\cdot\frac{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+1)})}{\Phi'(\mathrm{SOL})}.
\end{aligned} Φ ( ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j + 1 ( i + 1 ) ) = Φ ( ALG ρ , j ( i + 1 ) ∖ S ∗ ) − Φ ( S ∗ ∖ ALG ρ , j ( i + 1 ) ) ≥ d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) ⋅ Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) ⋅ Φ ′ ( SOL ) Φ ′ ( S ∗ ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ∗ ) = d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) ⋅ Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 1 ) ) . We are now ready to sum this over all iterations of the forward phase:
Φ ( A L G ρ , 0 ( i + 1 ) ) − Φ ( A L G ρ , J ( i + 1 ) ) = ∑ j = 0 J − 1 [ Φ ( A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j + 1 ( i + 1 ) ) ] ≥ ∑ j = 0 J − 1 ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ ⋅ Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) Φ ′ ( A L G ρ , j + 1 ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ) Φ ′ ( S O L ) ≥ ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ ∑ j = 0 J − 1 [ Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ , j ( i + 1 ) ) ] ⋅ Φ ′ ( A L G ρ , j + 1 ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ) Φ ′ ( S O L ) ≥ ( Γ − 1 ) ( Γ − 1 − ε ) d ( 1 + ε ) Γ ∑ j = 0 J − 1 [ Φ ( A L G ρ , J ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ , J ( i + 1 ) ) ] ⋅ Φ ′ ( A L G ρ , j + 1 ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ) Φ ′ ( S O L ) ≥ ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) d 2 ( 1 + ε ) Γ 2 Φ ( A L G ρ , J ( i + 1 ) ∖ S O L ) Φ ′ ( S O L ) ∑ j = 0 J − 1 [ Φ ′ ( A L G ρ , j + 1 ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ) ] = ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) d 2 ( 1 + ε ) Γ 2 Φ ( A L G ρ , J ( i + 1 ) ∖ S O L ) Φ ′ ( A L G ρ , J ( i + 1 ) ) − Φ ′ ( A L G ρ , 0 ( i + 1 ) ) Φ ′ ( S O L ) ≥ ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 Φ ( A L G ρ , J ( i + 1 ) ∖ S O L ) . \begin{aligned}
\Phi(\mathrm{ALG}_{\rho,0}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,J}^{(i+1)})
=\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+1)})\right] \\
&\ge\sum_{j=0}^{J-1}\frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d(1+\varepsilon)\Gamma}\cdot\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)}\setminus\mathrm{SOL})\frac{\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)})}{\Phi'(\mathrm{SOL})} \\
&\ge\frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d(1+\varepsilon)\Gamma}\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)}\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,j}^{(i+1)})\right]\cdot\frac{\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)})}{\Phi'(\mathrm{SOL})} \\
&\ge\frac{(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d(1+\varepsilon)\Gamma}\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,J}^{(i+1)}\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,J}^{(i+1)})\right]\cdot\frac{\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)})}{\Phi'(\mathrm{SOL})} \\
&\ge\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d^2(1+\varepsilon)\Gamma^2}\frac{\Phi(\mathrm{ALG}_{\rho,J}^{(i+1)}\setminus\mathrm{SOL})}{\Phi'(\mathrm{SOL})}\sum_{j=0}^{J-1}\left[\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)})\right] \\
&=\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)}{d^2(1+\varepsilon)\Gamma^2}\Phi(\mathrm{ALG}_{\rho,J}^{(i+1)}\setminus\mathrm{SOL})\frac{\Phi'(\mathrm{ALG}_{\rho,J}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,0}^{(i+1)})}{\Phi'(\mathrm{SOL})} \\
&\ge\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\Phi(\mathrm{ALG}_{\rho,J}^{(i+1)}\setminus\mathrm{SOL}).
\end{aligned} Φ ( ALG ρ , 0 ( i + 1 ) ) − Φ ( ALG ρ , J ( i + 1 ) ) = j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j + 1 ( i + 1 ) ) ] ≥ j = 0 ∑ J − 1 d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) ⋅ Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) Φ ′ ( SOL ) Φ ′ ( ALG ρ , j + 1 ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ) ≥ d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 1 ) ) ] ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j + 1 ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ) ≥ d ( 1 + ε ) Γ ( Γ − 1 ) ( Γ − 1 − ε ) j = 0 ∑ J − 1 [ Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , J ( i + 1 ) ) ] ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j + 1 ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ) ≥ d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) Φ ′ ( SOL ) Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) j = 0 ∑ J − 1 [ Φ ′ ( ALG ρ , j + 1 ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ) ] = d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) Φ ′ ( SOL ) Φ ′ ( ALG ρ , J ( i + 1 ) ) − Φ ′ ( ALG ρ , 0 ( i + 1 ) ) ≥ d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ Φ ( ALG ρ , J ( i + 1 ) ∖ SOL ) . The third-to-last inequality uses Lemma 7, which implies that Φ ( A L G ρ , j ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ , j ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho,j}^{(i+1)}\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,j}^{(i+1)}) Φ ( ALG ρ , j ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 1 ) ) Φ ( A L G ρ ( i + 1 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+1)}\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho}^{(i+1)}) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 1 ) ) Φ ′ ( A L G ρ , J ( i + 1 ) ) > ( d Γ ′ + κ ) χ ′ \Phi'(\mathrm{ALG}_{\rho,J}^{(i+1)})>(d\Gamma'+\kappa)\chi' Φ ′ ( ALG ρ , J ( i + 1 ) ) > ( d Γ ′ + κ ) χ ′ Φ ′ ( A L G ρ , 0 ( i + 1 ) ) ≤ d Γ ′ χ ′ \Phi'(\mathrm{ALG}_{\rho,0}^{(i+1)})\le d\Gamma'\chi' Φ ′ ( ALG ρ , 0 ( i + 1 ) ) ≤ d Γ ′ χ ′ χ ′ ≥ Φ ( S O L ) \chi'\ge\Phi(\mathrm{SOL}) χ ′ ≥ Φ ( SOL )
Lemma 17 (Backward Phase Analysis, generalizes Lemma 5.15 of [6 ] ). *Fix any even i + 2 i+2 i + 2 ρ \rho ρ A L G ρ ( i + 2 ) \mathrm{ALG}_{\rho}^{(i+2)} ALG ρ ( i + 2 ) Φ ( A L G ρ ( i + 2 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 2 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+2)}\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho}^{(i+2)}) Φ ( ALG ρ ( i + 2 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 2 ) ) T = Φ ′ ( A L G ρ ( i + 1 ) ) − Φ ′ ( A L G ρ ( i + 2 ) ) Φ ′ ( S O L ) T=\frac{\Phi'(\mathrm{ALG}_{\rho}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho}^{(i+2)})}{\Phi'(\mathrm{SOL})} T = Φ ′ ( SOL ) Φ ′ ( ALG ρ ( i + 1 ) ) − Φ ′ ( ALG ρ ( i + 2 ) ) ζ ′ = d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) \zeta'=\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)(d\Gamma'-1)(d\Gamma-1)} ζ ′ = ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) d ( 1 + ε ) Γ ′ A L G ρ ( i + 1 ) , A L G ρ ( i + 2 ) \mathrm{ALG}_{\rho}^{(i+1)},\mathrm{ALG}_{\rho}^{(i+2)} ALG ρ ( i + 1 ) , ALG ρ ( i + 2 )
Φ ( A L G ρ ( i + 2 ) ) − Φ ( A L G ρ ( i + 1 ) ) ≤ ( e ζ ′ T − 1 ) ⋅ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) . \Phi(\mathrm{ALG}_{\rho}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho}^{(i+1)})\le(e^{\zeta'T}-1)\cdot\Phi(\mathrm{ALG}_{\rho}^{(i+1)}\setminus\mathrm{SOL}). Φ ( ALG ρ ( i + 2 ) ) − Φ ( ALG ρ ( i + 1 ) ) ≤ ( e ζ ′ T − 1 ) ⋅ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . Proof. Because Φ ′ ( A L G ρ ( i + 2 ) ) ≥ d Γ ′ χ ′ \Phi'(\mathrm{ALG}_{\rho}^{(i+2)})\ge d\Gamma'\chi' Φ ′ ( ALG ρ ( i + 2 ) ) ≥ d Γ ′ χ ′ χ ′ ≥ Φ ′ ( S O L ) \chi'\ge\Phi'(\mathrm{SOL}) χ ′ ≥ Φ ′ ( SOL ) ϕ ′ \phi' ϕ ′ ε n χ ′ \frac{\varepsilon}{n}\chi' n ε χ ′ ε n \frac{\varepsilon}{n} n ε Φ ′ ( A L G ρ ( i + 2 ) ) \Phi'(\mathrm{ALG}_{\rho}^{(i+2)}) Φ ′ ( ALG ρ ( i + 2 ) )
We let A L G ρ , j ( i + 2 ) \mathrm{ALG}_{\rho,j}^{(i+2)} ALG ρ , j ( i + 2 ) A L G ρ ( i + 2 ) \mathrm{ALG}_{\rho}^{(i+2)} ALG ρ ( i + 2 ) j j j A L G ρ ( i + 2 ) \mathrm{ALG}_{\rho}^{(i+2)} ALG ρ ( i + 2 ) J J J A L G ρ , 0 ( i + 2 ) \mathrm{ALG}_{\rho,0}^{(i+2)} ALG ρ , 0 ( i + 2 ) A L G ρ ( i + 1 ) \mathrm{ALG}_{\rho}^{(i+1)} ALG ρ ( i + 1 ) A L G ρ ( i + 2 ) \mathrm{ALG}_{\rho}^{(i+2)} ALG ρ ( i + 2 ) A L G ρ , J ( i + 2 ) \mathrm{ALG}_{\rho,J}^{(i+2)} ALG ρ , J ( i + 2 )
Φ ( A L G ρ , J ( i + 2 ) ) − Φ ( A L G ρ , 0 ( i + 2 ) ) = ∑ j = 0 J − 1 [ Φ ( A L G ρ , j + 1 ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ) ] ≤ ( e ζ ′ T − 1 ) Φ ( A L G ρ , 0 ( i + 2 ) ∖ S O L ) . \Phi(\mathrm{ALG}_{\rho,J}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,0}^{(i+2)})=\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)})\right]\le(e^{\zeta'T}-1)\Phi(\mathrm{ALG}_{\rho,0}^{(i+2)}\setminus\mathrm{SOL}). Φ ( ALG ρ , J ( i + 2 ) ) − Φ ( ALG ρ , 0 ( i + 2 ) ) = j = 0 ∑ J − 1 [ Φ ( ALG ρ , j + 1 ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ) ] ≤ ( e ζ ′ T − 1 ) Φ ( ALG ρ , 0 ( i + 2 ) ∖ SOL ) . For each Φ ( A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j + 1 ( i + 2 ) ) \Phi(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+2)}) Φ ( ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j + 1 ( i + 2 ) ) Φ ′ ( A L G ρ ( i + 2 ) ) > d Γ ′ Φ ′ ( S O L ) \Phi'(\mathrm{ALG}_{\rho}^{(i+2)})>d\Gamma'\Phi'(\mathrm{SOL}) Φ ′ ( ALG ρ ( i + 2 ) ) > d Γ ′ Φ ′ ( SOL ) S ∈ Π A L G ρ , j ( i + 2 ) S O L S\in\Pi_{\mathrm{ALG}_{\rho,j}^{(i+2)}}^{\mathrm{SOL}} S ∈ Π ALG ρ , j ( i + 2 ) SOL
( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ∖ S ) Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ) − ( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 2 ) ) ≤ d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) Φ ( S O L ∖ A L G ρ , j ( i + 2 ) ) Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S O L ) . \frac{(1+\varepsilon)\Phi(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S)}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S)-(1+\varepsilon)\Phi'(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})}
\leq
\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)}
\frac{\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})}. Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S ) − ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 2 ) ) ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ∖ S ) ≤ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) d ( 1 + ε ) Γ ′ Φ ′ ( ALG ρ , j ( i + 2 ) ∖ SOL ) Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) . where Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ) − ( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 2 ) ) > 0 \Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S)-(1+\varepsilon)\Phi'(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})>0 Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S ) − ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 2 ) ) > 0
When GreedySwap is in the inner loop where W W W 1 + ε \sqrt{1+\varepsilon} 1 + ε Φ ′ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ′ ( A L G ρ , j ( i + 1 ) ∖ S ) \Phi'(S\setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+1)}\setminus S) Φ ′ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ′ ( ALG ρ , j ( i + 1 ) ∖ S ) W ′ W' W ′ 1 + ε \sqrt{1+\varepsilon} 1 + ε Φ ( S ∖ A L G ρ , j ( i + 1 ) ) − Φ ( A L G ρ , j ( i + 1 ) ∖ S ) \Phi(S\setminus\mathrm{ALG}_{\rho,j}^{(i+1)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+1)}\setminus S) Φ ( S ∖ ALG ρ , j ( i + 1 ) ) − Φ ( ALG ρ , j ( i + 1 ) ∖ S ) 1 + ε − 1 > 0 \sqrt{1+\varepsilon}-1>0 1 + ε − 1 > 0 ( 1 + ε ) (1+\varepsilon) ( 1 + ε ) 1 + ε \sqrt{1+\varepsilon} 1 + ε S ′ ∈ Π A L G ρ , j ( i + 2 ) S O L S'\in\Pi_{\mathrm{ALG}_{\rho,j}^{(i+2)}}^{\mathrm{SOL}} S ′ ∈ Π ALG ρ , j ( i + 2 ) SOL
Φ ′ ( S ′ ∖ A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ) \Phi'(S'\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S')\leq(1+\varepsilon)\Phi'(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S) Φ ′ ( S ′ ∖ ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S )
Φ ( S ′ ∖ A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ∖ S ) \Phi(S'\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S')\leq(1+\varepsilon)\Phi(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S) Φ ( S ′ ∖ ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ∖ S ′ ) ≤ ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ∖ S )
Therefore, the move S ∗ ∈ Π A L G ρ , j ( i + 2 ) S O L S^*\in\Pi_{\mathrm{ALG}_{\rho,j}^{(i+2)}}^{\mathrm{SOL}} S ∗ ∈ Π ALG ρ , j ( i + 2 ) SOL
Φ ( S ∗ ∖ A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ∖ S ∗ ) Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ∗ ) − Φ ′ ( S ∗ ∖ A L G ρ , j ( i + 2 ) ) ≤ Φ ( S ′ ∖ A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ∖ S ′ ) Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ′ ) − Φ ′ ( S ′ ∖ A L G ρ , j ( i + 2 ) ) ≤ ( 1 + ε ) Φ ( S ∖ A L G ρ , j ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ∖ S ) Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S ) − ( 1 + ε ) Φ ′ ( S ∖ A L G ρ , j ( i + 2 ) ) ≤ d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) Φ ( S O L ∖ A L G ρ , j ( i + 2 ) ) Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S O L ) ≤ d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) d Γ Φ ( A L G ρ , j ( i + 2 ) ∖ S O L ) Φ ′ ( S O L ) . \begin{aligned}
\frac{\Phi(S^*\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S^*)}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S^*)-\Phi'(S^*\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})}
\leq
\frac{\Phi(S'\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S')}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S')-\Phi'(S'\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})} \\
&\leq
\frac{(1+\varepsilon)\Phi(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S)}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus S)-(1+\varepsilon)\Phi'(S\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})} \\
&\leq
\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)}
\frac{\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})} \\
&\leq
\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)(d\Gamma'-1)d\Gamma}
\frac{\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})}{\Phi'(\mathrm{SOL})}.
\end{aligned} Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S ∗ ) − Φ ′ ( S ∗ ∖ ALG ρ , j ( i + 2 ) ) Φ ( S ∗ ∖ ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ∖ S ∗ ) ≤ Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S ′ ) − Φ ′ ( S ′ ∖ ALG ρ , j ( i + 2 ) ) Φ ( S ′ ∖ ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ∖ S ′ ) ≤ Φ ′ ( ALG ρ , j ( i + 2 ) ∖ S ) − ( 1 + ε ) Φ ′ ( S ∖ ALG ρ , j ( i + 2 ) ) ( 1 + ε ) Φ ( S ∖ ALG ρ , j ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ∖ S ) ≤ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) d ( 1 + ε ) Γ ′ Φ ′ ( ALG ρ , j ( i + 2 ) ∖ SOL ) Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ≤ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) d Γ d ( 1 + ε ) Γ ′ Φ ′ ( SOL ) Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) . The last inequality comes from the assumption that for all j < J j<J j < J Φ ( A L G ρ ( i + 2 ) ∖ S O L ) > d Γ ⋅ Φ ( S O L ∖ A L G ρ ( i + 2 ) ) \Phi(\mathrm{ALG}_{\rho}^{(i+2)}\setminus\mathrm{SOL})>d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho}^{(i+2)}) Φ ( ALG ρ ( i + 2 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ ( i + 2 ) ) Φ ′ ( A L G ρ , j ( i + 2 ) ) ≥ d Γ ′ Φ ′ ( S O L ) \Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})\geq d\Gamma'\Phi'(\mathrm{SOL}) Φ ′ ( ALG ρ , j ( i + 2 ) ) ≥ d Γ ′ Φ ′ ( SOL )
Φ ′ ( A L G ρ , j ( i + 2 ) ∖ S O L ) ≥ Φ ′ ( A L G ρ , j ( i + 2 ) ) − Φ ′ ( S O L ) ≥ ( d Γ ′ − 1 ) Φ ′ ( S O L ) . \Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})\geq\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{SOL})\geq(d\Gamma'-1)\Phi'(\mathrm{SOL}). Φ ′ ( ALG ρ , j ( i + 2 ) ∖ SOL ) ≥ Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( SOL ) ≥ ( d Γ ′ − 1 ) Φ ′ ( SOL ) . We can now compute:
Φ ( A L G ρ , J ( i + 2 ) ) − Φ ( A L G ρ , 0 ( i + 2 ) ) = ∑ j = 0 J − 1 [ Φ ( A L G ρ , j + 1 ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ) ] = ∑ j = 0 J − 1 Φ ( A L G ρ , j + 1 ( i + 2 ) ) − Φ ( A L G ρ , j ( i + 2 ) ) Φ ′ ( A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j + 1 ( i + 2 ) ) [ Φ ′ ( A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j + 1 ( i + 2 ) ) ] ≤ d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) d Γ ∑ j = 0 J − 1 [ Φ ( A L G ρ , j ( i + 2 ) ∖ S O L ) ] ⋅ Φ ′ ( A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j + 1 ( i + 2 ) ) Φ ′ ( S O L ) ≤ d ( 1 + ε ) Γ ′ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) ∑ j = 0 J − 1 [ Φ ( A L G ρ , j ( i + 2 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ , j ( i + 2 ) ) ] ⋅ Φ ′ ( A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j + 1 ( i + 2 ) ) Φ ′ ( S O L ) = ζ ′ ∑ j = 0 J − 1 [ Φ ( A L G ρ , j ( i + 2 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ , j ( i + 2 ) ) ] ⋅ Φ ′ ( A L G ρ , j ( i + 2 ) ) − Φ ′ ( A L G ρ , j + 1 ( i + 2 ) ) Φ ′ ( S O L ) . \begin{aligned}
\Phi(\mathrm{ALG}_{\rho,J}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,0}^{(i+2)})
&=\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)})\right]\\
&=\sum_{j=0}^{J-1}\frac{\Phi(\mathrm{ALG}_{\rho,j+1}^{(i+2)})-\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)})}{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+2)})}
\left[\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+2)})\right]\\
&\leq\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)(d\Gamma'-1)d\Gamma}
\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})\right]\cdot
\frac{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+2)})}{\Phi'(\mathrm{SOL})}\\
&\leq\frac{d(1+\varepsilon)\Gamma'}{(\sqrt{\Gamma'}-1)(\sqrt{\Gamma'}-1-\varepsilon)(d\Gamma'-1)(d\Gamma-1)}
\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})\right]\\
&\qquad\cdot\frac{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+2)})}{\Phi'(\mathrm{SOL})}\\
&=\zeta'\sum_{j=0}^{J-1}\left[\Phi(\mathrm{ALG}_{\rho,j}^{(i+2)}\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_{\rho,j}^{(i+2)})\right]\cdot
\frac{\Phi'(\mathrm{ALG}_{\rho,j}^{(i+2)})-\Phi'(\mathrm{ALG}_{\rho,j+1}^{(i+2)})}{\Phi'(\mathrm{SOL})}.
\end{aligned} Φ ( ALG ρ , J ( i + 2 ) ) − Φ ( ALG ρ , 0 ( i + 2 ) ) = j = 0 ∑ J − 1 [ Φ ( ALG ρ , j + 1 ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ) ] = j = 0 ∑ J − 1 Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) Φ ( ALG ρ , j + 1 ( i + 2 ) ) − Φ ( ALG ρ , j ( i + 2 ) ) [ Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) ] ≤ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) d Γ d ( 1 + ε ) Γ ′ j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) ] ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) ≤ ( Γ ′ − 1 ) ( Γ ′ − 1 − ε ) ( d Γ ′ − 1 ) ( d Γ − 1 ) d ( 1 + ε ) Γ ′ j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ] ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) = ζ ′ j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ] ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) . The last inequality comes from the assumption that
Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) \Phi(\operatorname{ALG}^{(i+2)}_{\rho,j} \setminus\operatorname{SOL}) > d\Gamma\cdot\Phi(\operatorname{SOL} \setminus\operatorname{ALG}^{(i+2)}_{\rho,j}) Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) > d Γ ⋅ Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) for all j ≤ J j \le J j ≤ J
Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) = d Γ d Γ − 1 Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − 1 d Γ − 1 Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) < d Γ d Γ − 1 [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ] . \begin{aligned}
\Phi(\operatorname{ALG}^{(i+2)}_{\rho,j} \setminus\operatorname{SOL}) = \frac{d\Gamma}{d\Gamma-1}\Phi(\operatorname{ALG}^{(i+2)}_{\rho,j} \setminus\operatorname{SOL}) - \frac{1}{d\Gamma-1}\Phi(\operatorname{ALG}^{(i+2)}_{\rho,j} \setminus\operatorname{SOL}) \\
&< \frac{d\Gamma}{d\Gamma-1}\left[\Phi(\operatorname{ALG}^{(i+2)}_{\rho,j} \setminus\operatorname{SOL})-\Phi(\operatorname{SOL} \setminus\operatorname{ALG}^{(i+2)}_{\rho,j})\right].
\end{aligned} Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) = d Γ − 1 d Γ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − d Γ − 1 1 Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) < d Γ − 1 d Γ [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ] . It now suffices to show:
∑ j = 0 J − 1 [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ] ⋅ Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) Φ ′ ( SOL ) ≤ \sum_{j=0}^{J-1}\left[\Phi(\operatorname{ALG}^{(i+2)}_{\rho,j} \setminus\operatorname{SOL})-\Phi(\operatorname{SOL} \setminus\operatorname{ALG}^{(i+2)}_{\rho,j})\right]\cdot\frac{\Phi'(\operatorname{ALG}^{(i+2)}_{\rho,j})-\Phi'(\operatorname{ALG}^{(i+2)}_{\rho,j+1})}{\Phi'(\operatorname{SOL})}
\le j = 0 ∑ J − 1 [ Φ ( ALG ρ , j ( i + 2 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ , j ( i + 2 ) ) ] ⋅ Φ ′ ( SOL ) Φ ′ ( ALG ρ , j ( i + 2 ) ) − Φ ′ ( ALG ρ , j + 1 ( i + 2 ) ) ≤ e ζ ′ T − 1 ζ ′ Φ ( ALG ρ , 0 ( i + 2 ) ∖ SOL ) . \frac{e^{\zeta'T}-1}{\zeta'}\Phi(\operatorname{ALG}^{(i+2)}_{\rho,0}\setminus\operatorname{SOL}). ζ ′ e ζ ′ T − 1 Φ ( ALG ρ , 0 ( i + 2 ) ∖ SOL ) . This is done at the end of the proof of Lemma 5.15 in [6 ] by analyzing the integral of a well-chosen function.
Lemma 19 (generalizes Lemma 5.17 from [6 ] ). Suppose Γ \Gamma Γ Γ ′ \Gamma' Γ ′ κ \kappa κ ε \varepsilon ε ζ ′ \zeta' ζ ′
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , \min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}\right\}-(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1)>0, min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , and 0 < ε < 2 3 − 5 3 d Γ 0<\varepsilon<\frac{2}{3}-\frac{5}{3d\Gamma} 0 < ε < 3 2 − 3 d Γ 5 Let η \eta η
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) 1 + d Γ d Γ − 1 ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) . \frac{\min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}\right\}-(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1)}{1+\frac{d\Gamma}{d\Gamma-1}(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1)}. 1 + d Γ − 1 d Γ ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) . Assume η > 0 \eta>0 η > 0 I = 2 ( ⌈ log n max i ∈ Ω ϕ ( i ) min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) log ( 1 + η ) ⌉ + 1 ) I=2\left(\left\lceil\frac{\log\frac{n\max_{i\in\Omega}\phi(i)}{\min_{\substack{i\in\Omega\\\phi(i)>0}}\phi(i)}}{\log(1+\eta)}\right\rceil+1\right) I = 2 l o g ( 1 + η ) l o g m i n i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) n m a x i ∈ Ω ϕ ( i ) + 1 ALG ∗ \operatorname{ALG}^{*} ALG ∗ ALG ρ ( i ) \operatorname{ALG}^{(i)}_{\rho} ALG ρ ( i ) DoubleApprox algorithm for some i ≤ I i\le I i ≤ I ρ \rho ρ Φ ( ALG ∗ ∖ SOL ) ≤ d Γ Φ ( SOL ∖ ALG ∗ ) \Phi(\operatorname{ALG}^{*}\setminus\operatorname{SOL})\le d\Gamma\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{*}) Φ ( ALG ∗ ∖ SOL ) ≤ d ΓΦ ( SOL ∖ ALG ∗ ) Φ ′ ( ALG ∗ ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL ) \Phi'(\operatorname{ALG}^{*})\le(d\Gamma'+\kappa+1+\varepsilon)\Phi'(\operatorname{SOL}) Φ ′ ( ALG ∗ ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL )
Proof. We let Δ ( i ) : = Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) \Delta(i):=\Phi(\operatorname{ALG}^{(i)}\setminus\operatorname{SOL})-\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)}) Δ ( i ) := Φ ( ALG ( i ) ∖ SOL ) − Φ ( SOL ∖ ALG ( i ) ) i i i Corollary 18 , for all i i i
Φ ′ ( ALG ρ ( i ) ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL ) . \Phi'(\operatorname{ALG}^{(i)}_{\rho})\le(d\Gamma'+\kappa+1+\varepsilon)\Phi'(\operatorname{SOL}). Φ ′ ( ALG ρ ( i ) ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL ) . Therefore, if the lemma is false, we have that for all i i i ρ \rho ρ
Φ ( ALG ρ ( i ) ∖ SOL ) > d Γ Φ ( SOL ∖ ALG ρ ( i ) ) . \Phi(\operatorname{ALG}^{(i)}_{\rho}\setminus\operatorname{SOL})>d\Gamma\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(i)}_{\rho}). Φ ( ALG ρ ( i ) ∖ SOL ) > d ΓΦ ( SOL ∖ ALG ρ ( i ) ) . By Corollary 18 , and under the assumption of the lemma that
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , \min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^{2}(1+\varepsilon)\Gamma^{2}}\right\}-(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1)>0, min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0 , we know that for all i i i Φ ( ALG ( i ) ) − Φ ( ALG ( i + 2 ) ) ≥ 0 \Phi(\operatorname{ALG}^{(i)})-\Phi(\operatorname{ALG}^{(i+2)})\ge0 Φ ( ALG ( i ) ) − Φ ( ALG ( i + 2 ) ) ≥ 0 Δ ( I ) < d Γ − 1 d Γ min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) \Delta(I)<\frac{d\Gamma-1}{d\Gamma}\min_{\substack{i\in\Omega\\\phi(i)>0}}\phi(i) Δ ( I ) < d Γ d Γ − 1 min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) Φ ( ALG ( I ) ∖ SOL ) > d Γ Φ ( SOL ∖ ALG ( I ) ) \Phi(\operatorname{ALG}^{(I)}\setminus\operatorname{SOL})>d\Gamma\Phi(\operatorname{SOL}\setminus\operatorname{ALG}^{(I)}) Φ ( ALG ( I ) ∖ SOL ) > d ΓΦ ( SOL ∖ ALG ( I ) ) Φ ( A L G ( I ) ∖ S O L ) − Φ ( S O L ∖ A L G ( I ) ) > d Γ − 1 d Γ Φ ( A L G ( I ) ∖ S O L ) \Phi(\mathrm{ALG}^{(I)} \setminus\mathrm{SOL})-\Phi(\mathrm{SOL} \setminus\mathrm{ALG}^{(I)}) > \frac{d\Gamma-1}{d\Gamma}\Phi(\mathrm{ALG}^{(I)} \setminus\mathrm{SOL}) Φ ( ALG ( I ) ∖ SOL ) − Φ ( SOL ∖ ALG ( I ) ) > d Γ d Γ − 1 Φ ( ALG ( I ) ∖ SOL ) d Γ d\Gamma d Γ Φ ( A L G ( I ) ∖ S O L ) > 0 \Phi(\mathrm{ALG}^{(I)} \setminus\mathrm{SOL}) > 0 Φ ( ALG ( I ) ∖ SOL ) > 0 Φ ( A L G ( I ) ∖ S O L ) > min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) \Phi(\mathrm{ALG}^{(I)} \setminus\mathrm{SOL}) > \min_{\substack{i\in\Omega\\\phi(i)>0}}\phi(i) Φ ( ALG ( I ) ∖ SOL ) > min i ∈ Ω ϕ ( i ) > 0 ϕ ( i )
Now, let us show how we reach this contradiction by studying how Δ ( i ) \Delta(i) Δ ( i ) Φ ( 0 ) ≤ n max i ∈ Ω ϕ ( i ) \Phi(0) \le n\max_{i\in\Omega}\phi(i) Φ ( 0 ) ≤ n max i ∈ Ω ϕ ( i ) Δ ( i ) − Δ ( i + 2 ) = Φ ( A L G ( i ) ) − Φ ( A L G ( i + 2 ) ) \Delta(i)-\Delta(i+2)=\Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}^{(i+2)}) Δ ( i ) − Δ ( i + 2 ) = Φ ( ALG ( i ) ) − Φ ( ALG ( i + 2 ) ) ρ \rho ρ ρ ∈ [ Φ ( A L G ( i ) ∖ S O L ) , ( 1 + ε ) Φ ( A L G ( i ) ∖ S O L ) ] \rho\in[\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL}), (1+\varepsilon)\Phi(\mathrm{ALG}^{(i)}\setminus\mathrm{SOL})] ρ ∈ [ Φ ( ALG ( i ) ∖ SOL ) , ( 1 + ε ) Φ ( ALG ( i ) ∖ SOL )]
Δ ( i ) − Δ ( i + 2 ) = Φ ( A L G ( i ) ) − Φ ( A L G ( i + 2 ) ) ≥ [ min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ c ( A L G ρ ( i + 1 ) ∖ S O L ) ≥ [ min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ [ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ ( i + 1 ) ) ] . \begin{aligned}
\Delta(i)-\Delta(i+2)
&=\Phi(\mathrm{ALG}^{(i)})-\Phi(\mathrm{ALG}^{(i+2)})\\
&\ge\left[\min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}-(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)\right]\\
&\qquad\cdot c(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})\\
&\ge\left[\min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}-(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)\right]\\
&\qquad\cdot[\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho)].
\end{aligned} Δ ( i ) − Δ ( i + 2 ) = Φ ( ALG ( i ) ) − Φ ( ALG ( i + 2 ) ) ≥ [ min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ c ( ALG ρ ( i + 1 ) ∖ SOL ) ≥ [ min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ] ⋅ [ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) )] . Since we have assumed that Φ ( A L G ρ ( i + 1 ) ∖ S O L ) > d Γ Φ ( S O L ∖ A L G ρ ( i + 1 ) ) \Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})>d\Gamma\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) > d ΓΦ ( SOL ∖ ALG ρ ( i + 1 ) )
Φ ( A L G ρ ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ ( i + 1 ) ) > d Γ − 1 d Γ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) . \Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho)>\frac{d\Gamma-1}{d\Gamma}\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL}). Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) ) > d Γ d Γ − 1 Φ ( ALG ρ ( i + 1 ) ∖ SOL ) . We use this inequality, along with both Lemma 17, knowing that T ≤ d Γ ′ + κ + 1 + ε T\le d\Gamma'+\kappa+1+\varepsilon T ≤ d Γ ′ + κ + 1 + ε
Δ ( i + 2 ) − [ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ ( i + 1 ) ) ] ≤ ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) Φ ( A L G ρ ( i + 1 ) ∖ S O L ) < d Γ d Γ − 1 ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) [ Φ ( A L G ρ ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ ( i + 1 ) ) ] , \begin{aligned}
\Delta(i+2)-[\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho)]
&\le(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})\\
&<\frac{d\Gamma}{d\Gamma-1}(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)[\Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho)],
\end{aligned} Δ ( i + 2 ) − [ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) )] ≤ ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) Φ ( ALG ρ ( i + 1 ) ∖ SOL ) < d Γ − 1 d Γ ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) [ Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) )] , which implies:
Φ ( A L G ρ ( i + 1 ) ∖ S O L ) − Φ ( S O L ∖ A L G ρ ( i + 1 ) ) > 1 1 + d Γ d Γ − 1 ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) Δ ( i + 2 ) . \Phi(\mathrm{ALG}^{(i+1)}_\rho\setminus\mathrm{SOL})-\Phi(\mathrm{SOL}\setminus\mathrm{ALG}^{(i+1)}_\rho)>\frac{1}{1+\frac{d\Gamma}{d\Gamma-1}(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)}\Delta(i+2). Φ ( ALG ρ ( i + 1 ) ∖ SOL ) − Φ ( SOL ∖ ALG ρ ( i + 1 ) ) > 1 + d Γ − 1 d Γ ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) 1 Δ ( i + 2 ) . Now, we merge this inequality into our lower bound of Δ ( i ) − Δ ( i + 2 ) \Delta(i)-\Delta(i+2) Δ ( i ) − Δ ( i + 2 )
Φ ( i + 2 ) < ( 1 + min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) 1 + d Γ d Γ − 1 ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) ) − 1 Φ ( i ) = ( 1 + η ) − 1 Φ ( i ) . \begin{aligned}
\Phi(i+2)&<\left(1+\frac{\min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}-(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)}{1+\frac{d\Gamma}{d\Gamma-1}(e^{\xi'(d\Gamma'+\kappa+1+\varepsilon)}-1)}\right)^{-1}\Phi(i)\\
&=(1+\eta)^{-1}\Phi(i).
\end{aligned} Φ ( i + 2 ) < 1 + 1 + d Γ − 1 d Γ ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ξ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) − 1 Φ ( i ) = ( 1 + η ) − 1 Φ ( i ) . Therefore, Δ ( i ) < ( 1 + η ) − i / 2 Δ ( 0 ) ≤ ( 1 + η ) − i / 2 n max i ∈ Ω ϕ ( i ) \Delta(i)<(1+\eta)^{-i/2}\Delta(0)\le(1+\eta)^{-i/2}n\max_{i\in\Omega}\phi(i) Δ ( i ) < ( 1 + η ) − i /2 Δ ( 0 ) ≤ ( 1 + η ) − i /2 n max i ∈ Ω ϕ ( i ) i = I i=I i = I Δ ( I ) < min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) \Delta(I)<\min_{\substack{i\in\Omega\\\phi(i)>0}}\phi(i) Δ ( I ) < min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) □ \square □
Lemma 15 (generalizes Lemma 5.5 of [6 ] ). Let S O L \mathrm{SOL} SOL P P P ( x , r ) (x,r) ( x , r ) x x x w w w w ′ w' w ′ w i = u i x i + ℓ i ( 1 − x i ) w_i=u_ix_i+\ell_i(1-x_i) w i = u i x i + ℓ i ( 1 − x i ) w i ′ = ℓ i ( 1 − x i ) w'_i=\ell_i(1-x_i) w i ′ = ℓ i ( 1 − x i ) Γ ′ > 1 \Gamma'>1 Γ ′ > 1 κ > 0 \kappa>0 κ > 0 0 < ε < 1 / 4 0<\varepsilon<1/4 0 < ε < 1/4 Γ \Gamma Γ A L G \mathrm{ALG} ALG A L G j \mathrm{ALG}_j ALG j
w ( A L G j ∖ S O L ) ≤ d Γ Λ ⋅ w ( S O L ∖ A L G j ) w(\mathrm{ALG}_j\setminus\mathrm{SOL})\le d\Gamma\Lambda\cdot w(\mathrm{SOL}\setminus\mathrm{ALG}_j) w ( ALG j ∖ SOL ) ≤ d ΓΛ ⋅ w ( SOL ∖ ALG j )
w ′ ( A L G j ) ≤ ( d Γ ′ + κ + 1 + ε ) Λ w ′ ( S O L ) w'(\mathrm{ALG}_j)\le(d\Gamma'+\kappa+1+\varepsilon)\Lambda w'(\mathrm{SOL}) w ′ ( ALG j ) ≤ ( d Γ ′ + κ + 1 + ε ) Λ w ′ ( SOL )
Proof. One important remark here is that either Φ ( S O L ) \Phi(\mathrm{SOL}) Φ ( SOL ) Φ ′ ( S O L ) \Phi'(\mathrm{SOL}) Φ ′ ( SOL ) Φ ≥ Φ ′ \Phi\geq\Phi' Φ ≥ Φ ′ Φ ′ ( S O L ) = 0 \Phi'(\mathrm{SOL}) = 0 Φ ′ ( SOL ) = 0 Φ ( S O L ) > 0 \Phi(\mathrm{SOL}) > 0 Φ ( SOL ) > 0 Φ ′ ( S O L ) = Φ ( S O L ) = 0 \Phi'(\mathrm{SOL}) = \Phi(\mathrm{SOL}) = 0 Φ ′ ( SOL ) = Φ ( SOL ) = 0 i i i ϕ ( i ) = 0 ⟺ w i = 0 \phi(i) = 0 \Longleftrightarrow w_i = 0 ϕ ( i ) = 0 ⟺ w i = 0 ϕ ′ ( i ) = 0 ⟺ w i ′ = 0 \phi'(i) = 0 \Longleftrightarrow w'_i = 0 ϕ ′ ( i ) = 0 ⟺ w i ′ = 0
In case (a), Φ ′ ( S O L ) = 0 \Phi'(\mathrm{SOL}) = 0 Φ ′ ( SOL ) = 0 w ′ ( S O L ) = 0 w'(\mathrm{SOL}) = 0 w ′ ( SOL ) = 0 w ′ w' w ′ A L G j \mathrm{ALG}_j ALG j w ′ ( A L G j ) = 0 w'(\mathrm{ALG}_j) = 0 w ′ ( ALG j ) = 0 Ω 0 ⊆ Ω \Omega_0 \subseteq\Omega Ω 0 ⊆ Ω w ′ w' w ′ w w w Lemma 8 ensures that we get some solution that is a γ \gamma γ w w w γ \gamma γ d ≥ λ d \geq\lambda d ≥ λ
In case (b), we have w ( S O L ) = w ′ ( S O L ) = 0 w(\mathrm{SOL}) = w'(\mathrm{SOL}) = 0 w ( SOL ) = w ′ ( SOL ) = 0 w ′ ( A L G j ) = 0 w'(\mathrm{ALG}_j) = 0 w ′ ( ALG j ) = 0 w ( A L G j ∖ S O L ) = 0 w(\mathrm{ALG}_j \setminus\mathrm{SOL}) = 0 w ( ALG j ∖ SOL ) = 0 w ( S O L ) = 0 w(\mathrm{SOL}) = 0 w ( SOL ) = 0 w ( A L G j ) = 0 w(\mathrm{ALG}_j) = 0 w ( ALG j ) = 0 Ω 00 ⊆ Ω \Omega_{00} \subseteq\Omega Ω 00 ⊆ Ω i ∈ Ω i \in\Omega i ∈ Ω w ( i ) = w ′ ( i ) = 0 w(i) = w'(i) = 0 w ( i ) = w ′ ( i ) = 0
This concludes the analysis in the case where Φ ( S O L ) = 0 \Phi(\mathrm{SOL}) = 0 Φ ( SOL ) = 0 Φ ′ ( S O L ) = 0 \Phi'(\mathrm{SOL}) = 0 Φ ′ ( SOL ) = 0 Φ ( S O L ) ≥ min i ∈ Ω ϕ ( i ) ≠ 0 ϕ ( i ) \Phi(\mathrm{SOL}) \geq\min_{i\in\Omega\atop\phi(i)\neq0} \phi(i) Φ ( SOL ) ≥ min ϕ ( i ) = 0 i ∈ Ω ϕ ( i ) Φ ′ ( S O L ) ≥ min i ∈ Ω ϕ ′ ( i ) ≠ 0 ϕ ′ ( i ) \Phi'(\mathrm{SOL}) \geq\min_{i\in\Omega\atop\phi'(i)\neq0} \phi'(i) Φ ′ ( SOL ) ≥ min ϕ ′ ( i ) = 0 i ∈ Ω ϕ ′ ( i )
We now assume that we have χ ∈ [ Φ ( S O L ) , ( 1 + ε ) Φ ( S O L ) ] \chi\in[\Phi(\mathrm{SOL}), (1+\varepsilon)\Phi(\mathrm{SOL})] χ ∈ [ Φ ( SOL ) , ( 1 + ε ) Φ ( SOL )] χ ′ ∈ [ Φ ′ ( S O L ) , ( 1 + ε ) Φ ′ ( S O L ) ] \chi' \in[\Phi'(\mathrm{SOL}), (1+\varepsilon)\Phi'(\mathrm{SOL})] χ ′ ∈ [ Φ ′ ( SOL ) , ( 1 + ε ) Φ ′ ( SOL )] Φ ′ \Phi' Φ ′ ε n χ ′ \frac{\varepsilon}{n}\chi' n ε χ ′
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0. \min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}-(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1)>0. min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) > 0. We show that there exists some large enough Γ > 1 \Gamma>1 Γ > 1 ζ ′ → Γ → ∞ 0 \zeta'\xrightarrow{\Gamma\to\infty}0 ζ ′ Γ → ∞ 0
min { d Γ − 1 2 d Γ , ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ d 2 ( 1 + ε ) Γ 2 } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) \min\left\{\frac{d\Gamma-1}{2d\Gamma},\frac{(d\Gamma-1)(\sqrt{\Gamma}-1)(\sqrt{\Gamma}-1-\varepsilon)\kappa}{d^2(1+\varepsilon)\Gamma^2}\right\}-(e^{\zeta'(d\Gamma'+\kappa+1+\varepsilon)}-1) min { 2 d Γ d Γ − 1 , d 2 ( 1 + ε ) Γ 2 ( d Γ − 1 ) ( Γ − 1 ) ( Γ − 1 − ε ) κ } − ( e ζ ′ ( d Γ ′ + κ + 1 + ε ) − 1 ) → Γ → ∞ min { 1 2 , κ d ( 1 + ε ) } > 0. \xrightarrow{\Gamma\to\infty}\min\left\{\frac{1}{2},\frac{\kappa}{d(1+\varepsilon)}\right\}>0. Γ → ∞ min { 2 1 , d ( 1 + ε ) κ } > 0. Since Γ > 1 \Gamma>1 Γ > 1 ε < 1 / 4 \varepsilon<1/4 ε < 1/4 ε < 2 / 3 − 5 3 d Γ \varepsilon<2/3-\frac{5}{3d\Gamma} ε < 2/3 − 3 d Γ 5 A L G j \mathrm{ALG}_j ALG j Φ ( A L G j ∖ S O L ) ≤ d Γ ⋅ Φ ( S O L ∖ A L G j ) \Phi(\mathrm{ALG}_j\setminus\mathrm{SOL})\leq d\Gamma\cdot\Phi(\mathrm{SOL}\setminus\mathrm{ALG}_j) Φ ( ALG j ∖ SOL ) ≤ d Γ ⋅ Φ ( SOL ∖ ALG j ) Φ ′ ( A L G j ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( S O L ) \Phi'(\mathrm{ALG}_j)\leq(d\Gamma'+\kappa+1+\varepsilon)\Phi'(\mathrm{SOL}) Φ ′ ( ALG j ) ≤ ( d Γ ′ + κ + 1 + ε ) Φ ′ ( SOL ) w ( A L G j ∖ S O L ) ≤ d Γ Λ ⋅ w ( S O L ∖ A L G j ) w(\mathrm{ALG}_j\setminus\mathrm{SOL})\leq d\Gamma\Lambda\cdot w(\mathrm{SOL}\setminus\mathrm{ALG}_j) w ( ALG j ∖ SOL ) ≤ d ΓΛ ⋅ w ( SOL ∖ ALG j ) w ′ ( A L G j ) ≤ ( d Γ ′ + κ + 1 + ε ) Λ w ′ ( S O L ) w'(\mathrm{ALG}_j)\leq(d\Gamma'+\kappa+1+\varepsilon)\Lambda w'(\mathrm{SOL}) w ′ ( ALG j ) ≤ ( d Γ ′ + κ + 1 + ε ) Λ w ′ ( SOL )
Therefore, the set of ALG of solutions that contains the guarantees of the lemma can be composed of the solution computed in cases (a) and (b), along with all the solutions returned by the DoubleApprox algorithm.
Now, we show that we can indeed find this special solution A L G j \mathrm{ALG}_j ALG j m = min i ∈ Ω ϕ ( i ) > 0 ϕ ( i ) m=\min_{i\in\Omega\atop\phi(i)>0}\phi(i) m = min ϕ ( i ) > 0 i ∈ Ω ϕ ( i ) m ′ = min i ∈ Ω ϕ ′ ( i ) > 0 ϕ ′ ( i ) m'=\min_{i\in\Omega\atop\phi'(i)>0}\phi'(i) m ′ = min ϕ ′ ( i ) > 0 i ∈ Ω ϕ ′ ( i ) ( χ , χ ′ ) (\chi,\chi') ( χ , χ ′ )
χ ∈ { m , 1 + ε m , … , 1 + ε ⌈ log 1 + ε ( n max i ∈ Ω ϕ ( i ) m ) ⌉ m } \chi\in\left\{m,\sqrt{1+\varepsilon}m,\ldots,\sqrt{1+\varepsilon}^{\left\lceil\log_{\sqrt{1+\varepsilon}}\left(\frac{n\max_{i\in\Omega}\phi(i)}{m}\right)\right\rceil}m\right\} χ ∈ { m , 1 + ε m , … , 1 + ε ⌈ l o g 1 + ε ( m n m a x i ∈ Ω ϕ ( i ) ) ⌉ m } and
χ ′ ∈ { m ′ , 1 + ε m ′ , … , 1 + ε ⌈ log 1 + ε ( n max i ∈ Ω ϕ ′ ( i ) m ′ ) ⌉ m ′ } . \chi'\in\left\{m',\sqrt{1+\varepsilon}m',\ldots,\sqrt{1+\varepsilon}^{\left\lceil\log_{\sqrt{1+\varepsilon}}\left(\frac{n\max_{i\in\Omega}\phi'(i)}{m'}\right)\right\rceil}m'\right\}. χ ′ ∈ { m ′ , 1 + ε m ′ , … , 1 + ε ⌈ l o g 1 + ε ( m ′ n m a x i ∈ Ω ϕ ′ ( i ) ) ⌉ m ′ } . These two sets are polynomially sized. When we call DoubleApprox for some value χ ′ \chi' χ ′ Φ ′ \Phi' Φ ′ ε n χ ′ \frac{\varepsilon}{n}\chi' n ε χ ′ ϕ ′ ( i ) \phi'(i) ϕ ′ ( i ) ⌈ ϕ ′ ( i ) ε n χ ′ ⌉ ε n χ ′ \left\lceil\frac{\phi'(i)}{\frac{\varepsilon}{n}\chi'}\right\rceil\frac{\varepsilon}{n}\chi' ⌈ n ε χ ′ ϕ ′ ( i ) ⌉ n ε χ ′ O ( ε ) O(\varepsilon) O ( ε )
Finally, each call of DoubleApprox runs in polynomial time. We have shown in Lemma 19 that the loop in Line 6 of DoubleApprox stops after a polynomial number of iterations. The forward loop in Line 10 cannot run for more than 5 n 2 5n^2 5 n 2 Φ \Phi Φ 1 10 n 2 ρ \frac{1}{10n^2}\rho 10 n 2 1 ρ ρ / 2 \rho/2 ρ /2 Φ ′ \Phi^{\prime} Φ ′ d Γ ′ / χ ′ d\Gamma^{\prime}/\chi^{\prime} d Γ ′ / χ ′ Corollary 18 , the potential Φ ′ \Phi^{\prime} Φ ′ ( d Γ ′ + κ + 1 + ε ) χ ′ (d\Gamma^{\prime}+\kappa+1+\varepsilon)\chi^{\prime} ( d Γ ′ + κ + 1 + ε ) χ ′ ε n χ ′ \frac{\varepsilon}{n}\chi^{\prime} n ε χ ′ ( κ + 1 + ε ) n ε (\kappa+1+\varepsilon)\frac{n}{\varepsilon} ( κ + 1 + ε ) ε n
