1. A method for new application instance placement in a set of machines under one or more resource constraints, the method comprising the steps of: computing an estimate of a value of a first metric associated with a current application instance placement and a current application load distribution; and determining the new application instance placement and a new application load distribution that optimizes the first metric, wherein the determining step further comprises: the new application instance placement improving upon the first metric and the new application load distribution improving upon a second metric; shifting an application load; changing the current application instance placement without pinning to determine a first candidate placement; changing the current application instance placement with pinning to determine a second candidate placement; and selecting a best placement from the first candidate placement and the second candidate placement as the new application instance placement; wherein the computing and determining steps are performed at least in part by a processor coupled to a memory.