Application placement on a cluster of servers. (English) Zbl 1202.68486

Summary: The Application Placement Problem (APP) 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.


68W25 Approximation algorithms
Full Text: DOI


[1] DOI: 10.1016/0304-3975(76)90048-7 · Zbl 0359.90053 · doi:10.1016/0304-3975(76)90048-7
[2] Cook W., INFORMS Journal on Computing pp 138–
[3] Cormen T., Introduction to Algorithms (1991)
[4] Hochbaum D. S., Approximation Algorithms for NP-hard Problems (1996) · Zbl 1368.68010
[5] Edmonds J., Journal of Research of the National Bureau of Standards B 69
[6] Friexe A. M., European Journal of Operational Research 15
[7] Garey M., Computers and Intractibility: A Guide to the Theory of NP-completeness (1979)
[8] Moser M., IEICE Trans. Fundamentals E 80
[9] DOI: 10.1007/BF02579324 · Zbl 0651.90052 · doi:10.1007/BF02579324
[10] DOI: 10.1007/BF01585178 · Zbl 0804.90077 · doi:10.1007/BF01585178
[11] DOI: 10.1007/978-3-642-68952-9 · doi:10.1007/978-3-642-68952-9
[12] K. L. Clark, Logic and Data Bases, eds. H. Gallaire and J. Winker (Plenum Press, New York, 1973) pp. 293–306.
[13] Joliat M., IEEE Trans. Comput. 27 pp 753–
[14] DOI: 10.1016/0022-0000(83)90050-8 · Zbl 0544.68010 · doi:10.1016/0022-0000(83)90050-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.