Approximation algorithms for a virtual machine allocation problem with finite types

We study the virtual machine allocation (VMA) problem with physical machines (PMs) of identical configuration and virtual machines (VMs) of a constant number of types. Only CPU and memory (MEM) resources are considered, so it is a special two-dimensional vector bin packing (2-DVBP) problem. Applying the best fit heuristic, we develop a fast online algorithm, which uses [Formula presented] PMs at most, where OPT(L) is the optimal value. According to the limited types of VMs, the progress of combining VMs and dividing the PMs' capacity contributes to a linear-time offline algorithm that uses [Formula presented] PMs. It outperforms the state-of-the-art (1.405+ϵ)-asymptotic approximation algorithm for the general 2-DVBP problem. These ideas can be extended to develop fast and practical algorithms.