Application placement on a cluster of servers

The APPLICATION PLACEMENT PROBLEM (APP, for short) arises in hosting platforms: clusters of servers that are used for hosting large, distributed applications such as Internet services. Hosting platforms imply a business relationship between an entity called the platform provider and a number of entities called the application providers. The latter pay the former for the resources on the hosting platform, in return for which, the former provides guarantees on resource availability for the applications. This implies that a hosting platform should host only applications for which it has sufficient resources. The objective of the APP is to maximize the number of applications that can be hosted on the platform while satisfying their resource requirements. The complexity of the APP is studied here, with the following results. The general APP is NP-hard; indeed, even restricted versions of the APP may not admit polynomial-time approximation schemes. However, several significant variants of the online version of the APP admit efficient approximation algorithms.