Algorithmics and Complexity of Cost-Driven Task Offloading with Submodular Optimization in Edge-Cloud Environments

Emerging applications such as autonomous driving pose the challenge of efficient cost-driven offloading in edge-cloud environments. This involves assigning tasks to edge and cloud servers for separate execution, with the goal of minimizing the total service cost including communication and computation costs. In this paper, observing that the intra-cloud communication costs are relatively low and can often be neglected in many real-world applications, we consequently introduce the so-called communication assumption which posits that the intra-cloud communication costs are not higher than the inter-partition communication cost between cloud and edge servers, nor the cost among edge servers. As a preliminary analysis, we first prove that the offloading problem without the communication assumption is NP-hard, using a reduction from MAX-CUT. Then, we show that the offloading problem can be modeled as a submodular minimization problem, making it polynomially solvable. Moreover, this polynomial solvability remains even when additional constraints are imposed, such as when certain tasks must be executed on edge servers due to latency constraints. By combining both algorithmics and computational complexity results, we demonstrate that the difficulty of the offloading problem largely depends on whether the communication assumption is satisfied. Lastly, extensive experiments are conducted to evaluate the practical performance of the proposed algorithm, demonstrating its significant advantages over the state-of-the-art methods in terms of efficiency and cost-effectiveness.