In this paper we consider the problem of initial resource selection for a single-domain fog provider lacking sufficient resources for the complete deployment of a batch of IoT applications. To overcome resources shortage, it is possible to lease assets from other domains across a federation of cloud-fog infrastructures to meet the requirements of those applications: the fog provider seeks to minimise the number of external resources to be rented in order to successfully deploy the applications’ demands exceeding own infrastructure capacity. To this aim, we introduce a general framework for the deployment of applications across multiple domains of cloud-fog providers while guaranteeing resources locality constraints. The resource allocation problem is presented in the form of an integer linear program, and we provide a heuristic method that explores the resource assignment space in a breadth-first fashion. Extensive numerical results demonstrate the efficiency of the proposed approach in terms of deployment cost and feasibility with respect to standard approaches adopted in the literature.