Exact and Approximation Algorithms for Task Offloading with Service Caching and Dependency in Mobile Edge Computing

With the continuous development of the Internet of Things (IoT) and communication technologies, the demand for low latency in practical applications is becoming increasingly significant. Mobile edge computing, as a promising computational model, is receiving growing attention. However, most existing studies fail to consider two critical factors: task dependency and service caching. Additionally, the majority of proposed solutions are not related to the optimal solution. We investigate the task offloading problem in mobile edge computing. Considering the requirements of applications for service caching and task dependency, we define an optimization problem to minimize the delay under the constraint of maximum completion cost and present a ( 1 + ϵ ) -approximation algorithm and an exact algorithm. Specifically, the offloading scheme is determined based on the relationships between tasks as well as the cost and delay incurred by data transmission and task execution. Simulation results demonstrate that in all cases, the offloading schemes obtained by our algorithm consistently outperform other algorithms. Moreover, the approximation ratio to the optimal solution from the approximation algorithm is validated to be less than ( 1 + ϵ ) , and the exact algorithm consistently produces the optimal solution.