Approximation Algorithm for the Offloading Problem in Edge Computing

In the edge-cloud environment, offloading technique decides the task to be executed either at the cloud or at the edge. Offloading can improve the quality of service and the efficiency of the system. In most previous works on the offloading problem, the communication costs between tasks on both cloud side or the edge side are often ignored. We consider a general offloading model where the communication costs between any two tasks is non-zero and asymmetric. Moreover, due to the resource limitation on the edge side, we assume that the number of tasks executed on the edge side is bounded by a fixed constant k. This generalized offloading problem is NP-hard in minimizing the total cost with cardinality constraint. Based on semidefinite program, we give an approximation algorithm with the performance guarantee of $$2/\pi $$ .