Approximation algorithms for a virtual machine allocation problem with finite types

作者：Guo, Lifeng^*; Lu, Changhong; Wu, Guanlin

来源：INFORMATION PROCESSING LETTERS, 2023, 180: 106339.

DOI：10.1016/j.ipl.2022.106339

• Cloud computing
• Divisible item sizes
• Virtual machine allocation
• Vector bin packing
• Approximation algorithms

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 209 O P T(L) + 1 PMs at most, where O P T(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 109 O P T(L) + 2 PMs. It outperforms the state-of-the-art (1.405 + E) -asymptotic approximation algorithm for the general 2-DVBP problem. These ideas can be extended to develop fast and practical algorithms.