1. A computer implemented method for generating a placement plan for one or more virtual machines (VMs) in a computing environment, the method comprising: providing, to a computing system, input parameters comprising: a current placement for the one or more VMs on one or more hosts in a computing network; a target placement that assigns at least one of the one or more VMs to at least another host in said one or more hosts; a set of constraints with which both the current placement and the target placement comply; and computing a placement plan to achieve the target placement for a target VM based on a placement sequence, wherein intermediary placement states are determined for the target VM according to the placement plan so that the target VM is migrated according to the placement sequence over one or more hosts in such a way to avoid a relocation cycle that results in a deadlock state in view of the set of constraints and the placement plan as applicable to other VMs, wherein the computation of the placement plan further comprises: computing a relocation graph that reflects placement changes for VM deployments, relocations or removals that are to be performed to implement the placement plan, wherein a node in the graph represents a host, and an edge in the graph pointing from a first node to a second node represents a planned VM relocation from a first host to a second host, the first node representing the first host and the second node representing the second host; breaking the relocation graph into one or more cores using the input parameters to the computing system, wherein a core comprises a first relocation graph that is smaller in size than the relocation graph; for a core, determining if the core is a simple core, wherein a core is determined to be simple if VMs in that core have same resource requirements and have no anti-collocation constraints; and in response to determining that the core is a simple core, applying a first solution to the first relocation graph to determine a relocation plan or a placement scheme for VMs in that core.