Cloud computing data enters dynamically provide millions of virtual machines (VMs) in actual cloud markets. In this context, Virtual Machine Placement (VMP) is one of the most challenging problems in cloud infrastructure management, considering the large number of possible optimization criteria and different formulations that could be studied. VMP literature include relevant research topics such as energy efficiency, Service Level Agreement (SLA), Quality of Service (QoS), cloud service pricing schemes and carbon dioxide emissions, all of them with high economical and ecological impact. This work classifies an extensive up-to-date survey of the most relevant VMP literature proposing a novel taxonomy in order to identify research opportunities and define a general vision on this research area.