Mobile devices, which are inherently of limited computing capabilities, face a growing demand to support increasingly complex applications. Computation offloading addresses this issue by enabling mobile devices to offload computations to a remote server. Advancing on previous work, this paper presents a cloud-based offloading service, which models an optimization problem with the objective of minimizing the operation cost of the service provider while achieving the agreed quality of service (QoS) for subscribers. The problem is shown to be A/75-hard. We propose a pseudo-polynomial-time optimal algorithm for the offline scenario, as well as an efficient online algorithm that has a provable QoS guarantee and allows practical implementations. To evaluate our algorithms, we synthesize remotable tasks and conduct extensive simulations based on real mobile user traces and application workload patterns. Our results demonstrate that our online algorithm could achieve comparable performance to the optimal offline algorithm, in terms of both the required cloud cost and the provided user benefit.