## 4 Approximation Algorithm
### Polynomial-Time Approximation Algorithm  
We use \(C(i,j,k)\) to represent the minimum completion cost of task \(i\) on device \(j\) under a maximum consumption delay of \(k\). The optimal strategy is derived by solving all subproblems for \(i\in[V]\) and \(j\in[M_{i}]\) of this problem. We do not solve all subproblems for \(k\in[1,UB]\), but instead discretize the delay values. \[q_{S}(x)=k,(k-1)S<x\leq KS,S=\frac{LBe}{L+1}. \tag{5}\]  
\(L\) denotes the depth of task graph (the greatest number of nodes contained within a single path). If all subproblems of a given problem have already been solved, the problem can be described as follows:  
\[k_{\text{add}}=q_{S}\Big{(}T_{j}^{m}+T_{ij}^{x_{i}m}\Big{)},k-k_{\text{add}}>=0. \tag{6}\]  
\[C_{\text{new}}(j,m,k)=C_{j}^{m}+\min_{x_{i}\in M_{i}}\sum_{i\in C(j)}\bigg{[} C_{ij}^{x_{i}m}+C(i,x_{i},k-\max_{i\in C(j)}k_{\text{add}})\bigg{]}. \tag{7}\]  
\(k_{\text{add}}\) represents the quantized value of transmission delay and execution delay. Equation (7) calculates the minimum cost that satisfies the maximum consumption delay \(k\) based on all feasible solutions, where \(\max_{i\in C(j)}k_{\text{add}}\) represents the slowest predecessor node in each feasible solution. Since the cost function (7) is additive, this implies that the minimum cost to complete task \(j\) on device \(m\) only depends on the sum of the costs of completing all its predecessor tasks and the data transmission cost. Furthermore, since all predecessor tasks of task \(j\) are independent of each other, this means that each predecessor task can be completed independently on different devices, and the data transmission process is also independent. As a result, the minimum value of the sum of the costs of completing all its predecessor tasks and the data transmission cost can be transformed into the sum of the minimum completion cost for each predecessor task and the corresponding transmission cost from that task \(i\) to task \(j\). Therefore, we can transform (7) into (8) while ensuring that the quality of the solution remains unchanged. At the same time, the solution space is reduced from \(M^{tp}\) to \(pM^{\prime}\), where \(p\) denotes the number of predecessor tasks for task \(j\), and \(M^{\prime}\) is the number of execution devices for task \(j\). \[C_{\text{new}}(j,m,k)=C_{j}^{m}+\sum_{i\in C(j)}\min_{x_{i}\in M_{i}}\bigg{[} C_{ij}^{x_{i}m}+C(i,x_{i},k-\max_{i\in C(j)}k_{\text{add}})\bigg{]}. \tag{8}\]After solving all subproblems of \(C(i,j,k)\), all the data needs to be aggregated to the local device \(a\). Therefore, the original problem can be transformed into the following form:  
\[\min k\quad\text{s.t.}\quad C(t,a,k)\leq T\]  
We propose an approximation algorithm to solve the task offloading problem, as shown in Algorithm 2. In lines 1 to 2, we initialize the minimum cost of all tasks when the maximum consumption delay is 0 to infinity, and set the virtual task \(s\) to have a minimum cost of 0 at the maximum consumption delay of 0, with the quantized value of \(UB\) being \(UB^{\prime}\). From lines 3 to 16, we compute the minimum cost for each task on the execution node that satisfies its service requirements, based on DP [41], under the constraint that the maximum consumption delay does not exceed \(k\). If a feasible solution with a delay constraint is found before \(k\) exceeds \(UB^{\prime}\), we return the corresponding offloading scheme. Otherwise, we return FAIL. ```
1:Initialize \(S\leftarrow\frac{LB}{L+1}\), \(C(v,m,0)\leftarrow\infty\) for all nodes \(v\in V\), \(m\in M_{v}\). 2:Set \(C(s,a,0)\gets 0\), \(U^{\prime}\leftarrow\left\lfloor\frac{UB}{S}\right\rfloor+L+1\). 3:for\(k=1,2,\ldots,U^{\prime}\)do
4:for\(j\in V\) in List I do
5:for\(m\in M_{j}\)do
6:\(C(j,m,k)\leftarrow\)\(C(j,m,k-1)\). Compute \(k_{\text{add}}\), \(C_{\text{new}}(j,m,k)\) according to (6) and (8). 7:if\(C_{\text{new}}(j,m,k)<C(j,m,k)\)then
8:\(C(j,m,k)\gets C_{\text{new}}(j,m,k)\). 9:if\(C(t,a,k)\leq T\)then
10:return the corresponding plan and delay.