Resource allocation in cloud computing is a challenging combinatorial problem due to dynamic workloads and strict resource constraints. In this paper, we present an Exact Cover formulation of the Virtual Machine (VM) to server allocation problem. By recasting allocation constraints into this framework, the problem becomes solvable using Algorithm X with Dancing Links (DLX), which enables constant-time cover/uncover operations and systematic exploration of feasible assignments. Experimental results on simulated cloud datasets show that the proposed DLX approach consistently achieves 100% allocation accuracy while significantly reducing execution time compared to metaheuristic methods such as Particle Swarm Optimization (PSO) and Genetic Algorithms (GA). For medium-scale scenarios, DLX runs up to 17x faster than PSO and 1.3x faster than GA, while producing more balanced server utilization. These findings highlight the effectiveness of modeling cloud resource allocation as an Exact Cover problem and solving it efficiently with Algorithm X and Dancing Links.

Keywords