Application placement on a cluster of servers

Bhuvan Urgaonkar, Arnold L. Rosenberg, Prashant Shenoy

Research output: Contribution to journalArticlepeer-review

59 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1023-1041
Number of pages19
JournalInternational Journal of Foundations of Computer Science
Issue number5
StatePublished - Oct 2007

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)


Dive into the research topics of 'Application placement on a cluster of servers'. Together they form a unique fingerprint.

Cite this