In Infrastructure-as-a-Server (IaaS) clouds, the provider has to decide on which server the virtual machines (VMs) requested by the users should be provisioned. This is an online scheduling problem, in which incoming VMs, typically with different resource requirements, have to be scheduled to one