||Mobile edge computing allows wireless users to exploit the power of cloud computing without the large communi- cation delay. To serve data-intensive applications (e.g., augmented reality, video analytics) from the edge, we need, in addition to CPU cycles and memory for computation, storage resource for storing server data and network bandwidth for receiving user- provided data. Moreover, the data placement needs to be adapted over time to serve time-varying demands, while considering system stability and operation cost. We address this problem by proposing a two-time-scale framework that jointly optimizes ser- vice (data & code) placement and request scheduling, under stor- age, communication, computation, and budget constraints. We fully characterize the complexity of our problem by analyzing the hardness of various cases. By casting our problem as a set func- tion optimization, we develop a polynomial-time algorithm that achieves a constant-factor approximation under certain condi- tions. Extensive synthetic and trace-driven simulations show that the proposed algorithm achieves 90% of the optimal performance. Index Terms—Mobile edge computing, service placement, re- source allocation, complexity analysis.