With the advent of resource virtualisation and disaggregation in 5th-generation mobile networks as well as Edge- and Fog-computing, forthcoming cloud infrastructures are poised to be geographically distributed and capability- and costheterogeneous. In the literature, this paradigm goes by many names, such as; Fog Computing [8], Telco-Cloud [10], Edgecloud [16], and Mobile Cloud [13], [14], [18]. Because of the network focus in this work, it is referred to as the Mobile Cloud Network (MCN) [17]. The MCN topological paradigm will proposedly enable and drive new types of services and applications that exploit the increased proximity to the end users and key infrastructure components.Contemporary cloud resources are housed in centralised Data Centres (DCs) that are separated from the end-users by the intermediate Wide Area Networks (WANs), core, and access networks. The added latency and weakbackhaul introduced by those networks has proven to inhibit the performance of cloud-based applications [2]. Furthermore, there is a large and growing set of mission critical realtime applications such as tele-robotic surgery [1], Radio Base Station (RBS) baseband signalling [11], gaming [15], and Augmented Reality (AR) [12] that are unable to operate in such a latency-, jitter-, and throughout-uncertain environment, provided by a centralised cloud paradigm. The decreased distance between the cloud infrastructure and the end-users, provided by an MCN, reduces the Round-Trip Time (RTT) and jitter, increases availability, and fault-tolerance [29] for the infrastructure’s resident cloud applications. To operate a viable MCN infrastructure, its operator needs to administer the admitted applications and the system’s resources such that; resources are not over-provisioned, total operational cost is minimised, and that all applications’ performance requirements are met. When managing an MCN, its operator’s primary degree of freedom is the placement of the system’s resident applications. Continuously and scalably evaluating the placement of a vast set of heterogeneous applications over a set of heterogeneous nodes is non-trivial and is the fundamental problem addressed in this paper. Optimally placing the resident applications in an MCN, given the constraints above, is NP-hard [27]. Furthermore, the optimal placement of the MCN’s resident applications was explored in our previous work [30], where it was concluded that a centralised solution is not scalable because it fundamentally fails to keep up with the system’s rate of change.