Abstract:A general multi-user mobile cloud computing system where each mobile user has multiple independent tasks is consided. These mobile users share the communication resource while offloading tasks to the cloud. How to jointly optimize the task offloading decisions of all users as well as the allocation of communication resource in order to minimize the overall cost of energy, computation, and delay for all users is one of the difficult problems in current research. The optimization problem is formulated as a non-convex Quadratically Constrained Quadratic Program(QCQP), which is NP-hard, and an efficient approximate algorithm is proposed by using separable Semi-Definite Relaxation(SDR) to solve this problem, followed by recovery of the binary offloading decision and optimal allocation of the communication resource. The simulation experiments are carried out by using the lower bound of the minimum system cost as the performance benchmark, the results show that the proposed algorithm gives nearly optimal performance under various parameter settings.