In cloud environment, virtualization supports server consolidation and a cloud service provider can improve resource utilization of physical machines and reduce power consumption through it. However, as physical machines are more consolidated, the probability of VM interference occurrence increases and it leads to the performance degradation in virtual machines. To solve this trade-off between reduction of VM interference and improvement of resource utilization of physical machines, we propose cost-efficient VM placement schemes including i) an algorithm for VM placement with Lyapunov optimization model and (ii) heuristics for VM placement based on VM interference quantizing scheme for cost-efficient VM placement schemes. The algorithm for VM placement with Lyapunov optimization model is discussed to initially find the best physical machine to place VMs minimizing the total cost of a SLA penalty cost and a physical machine management cost adaptively to VM interference. However, it causes high computational complexity in offline VM placement. Therefore, the heuristics for VM placement based on VM interference quantizing scheme is proposed for online initial VM placement to reduce complexity. A VM interference quantizing scheme is presented to estimate the current VM interference and predict VM interference after a new virtual machine is added to each physical machine. The experimental result shows that the VM interference quantizing scheme is performed precisely except for some cases and the heuristics can reduce the total cost more in comparison with the conventional VM placement schemes.