## 4 Approximation Algorithm
### Polynomial-Time Approximation Algorithm
11:endif
12:endif
13:endfor
14:endfor
15:endfor
16:return FAIL. ```  
**Algorithm 2** PTA(\(G(V,E)\), \(M_{v}\), \(UB\), \(LB\), \(T\), \(\epsilon\), List I)  
**Lemma 1**. : _Let \(x\) represent any offloading scheme, and let \(\tilde{d}(x)\) denote the quantized delay value of the offloading scheme \(x\). The delay of the offloading scheme \(x\) satisfies \(d(x)\leq\tilde{d}(x)S\leq d(x)+(L+1)S\)._  
Proof. : The proof is presented in Appendix A. However, since Algorithm 2 does not guarantee polynomial-time complexity, we present an approximate testing process of \(UB\) and \(LB\) (Algorithm 3), which iteratively invokes Algorithm 2 to reduce the gap between \(UB\) and \(LB\) as well as the quantization step size, thereby reducing the overall time complexity to guarantee polynomial-time complexity. ```
1:Set \(B_{L}\gets LB\), \(B_{U}\leftarrow\frac{UB}{1+e}\). 2:while\(\frac{B_{U}}{B_{L}}>2\)do
3:\(B\leftarrow\sqrt{B_{U}\times B_{L}}\). 4:if\(PTA(G(V,E),\,M_{v},\,B,\,B,\,T,\,e,\,\text{List I})\) returns FAIL then
5:\(\text{Test}(\epsilon,B)=\text{Yes}\), \(B_{L}\gets B\). 6:else
7:\(\text{Test}(\epsilon,B)=\text{No}\), \(B_{U}\gets B\). 8:endif
9:endwhile
10:return\(\text{PTA}(G(V,E),\,M_{v},\,(1+e)B_{U},\,B_{L},\,T,\,e,\,\text{List I})\). ```  
**Algorithm 3**\(\text{TUL}(G(V,E),\,UB,\,LB,\,T,\,e,\,\text{List I})\)  
Lemma 2: _If Test(\(\epsilon\),\(B\)) = Yes, when \(PTA(G(V,E),\,M_{v},\,B,\,B,\,T,\,e,\,\text{List I})\) returns FAIL, then \(d^{*}>B\); otherwise, \(d^{*}<(1+\epsilon)B\), where \(d^{*}\) represents the delay of the optimal solution._  
Proof: The proof is presented in Appendix B.  
Theorem 2: _Given valid bounds \(0<LB\leq d^{*}\leq UB\), by Lemma 1 and Lemma 2 we can obtain a \((1+\epsilon)\)-approximate result in \(O(d_{in}N^{\prime}{M^{\prime}}^{2}\frac{L}{\epsilon}(\log\log(UB/LB)+1))\) time._  
Proof: From Algorithm 2, each DP procedure solves \(N^{\prime}{M^{\prime}}U^{\prime}\) subproblems [32]. Let \(d_{in}\) denote the maximum indegree of the task graph. For solving each subproblem in equation 8, there can be up to \(d_{in}\) minimization problems across \(M^{\prime}\) devices. Consequently, the overall complexity of the procedure in Algorithm 3 can be bounded by  
\[O(d_{in}N^{\prime}{M^{\prime}}^{2}U^{\prime})=O\bigg{(}d_{in}N^{\prime}{M^{ \prime}}^{2}L\cdot\frac{UB}{LB\epsilon}+d_{in}N^{\prime}{M^{\prime}}^{2}L\bigg{)}.\]  
If \(UB\geq LB\), and \(\epsilon\leq 1\), then  
\[O(d_{in}N^{\prime}{M^{\prime}}^{2}U^{\prime})=O\bigg{(}d_{in}N^{\prime}{M^{ \prime}}^{2}L\cdot\frac{UB}{LB\epsilon}\bigg{)}.\]  
In Algorithm 1, we first compute the maximum delay \(UB\) and minimum delay \(LB\) for the problem without cost constraints, which serve as valid bounds. By Lemma 2, \(\text{Test}(\epsilon,B)\) is an effective process for reducing the dynamic range. Lines 4 to 8 in Algorithm 3 ensure that, at each iteration, \(B_{L}\) is a valid lower bound and \((1+\epsilon)B_{U}\) is a valid upper bound. In Algorithm 3, binary search is used to search for the boundary within the range of \(\log B_{L}\) to \(\log B_{U}\) until the condition \(B_{U}/B_{L}\leq 2\) is satisfied. During the iterative process, \(\log(B_{U}/B_{L})\) decreases to either \(\log(\sqrt{B_{U}B_{L}}/B_{L})\) or \(\log(B_{U}/\sqrt{B_{U}B_{L}})\). Since \(\log(\sqrt{B_{U}B_{L}}/B_{L})=\log\big{(}B_{U}/\sqrt{B_{U}B_{L}}\big{)}=\frac {1}{2}\log(B_{U}/B_{L})\), the dynamic range is halved after each iteration. Therefore, the binary search requires \(\log\log(UB/LB)\) calls to Algorithm 2. The complexity of lines 4 to 8 in Algorithm 3 is \(O(d_{in}N^{\prime}{M^{\prime}}^{2}\frac{L}{\epsilon}\log\log(UB/LB))\). Since \(UB/LB=(1+\epsilon)B_{U}/B_{L}=O(1)\) in line 10 of Algorithm 3, the complexity of line 10 in Algorithm 3 is \(O(d_{in}N^{\prime}{M^{\prime}}^{2}\frac{L}{\epsilon})\). Therefore, the total complexity is \(O(d_{in}N^{\prime}{M^{\prime}}^{2}\frac{L}{\epsilon}(\log\log(UB/LB)+1))\). According to Lemma 1, we assume \(x\) is the offloading scheme obtained by Algorithm 2, and \(x^{*}\) is the optimal offloading scheme.