1. A computer-implemented method for placing one or more guest computing system instances in a virtualized computing system, comprising: under the control of one or more computer systems configured with executable instructions, creating a placement map comprising regions corresponding to one or more available capacity measurements of one or more host machines in the virtualized computing system; and as a result of retrieving one or more capacity requests to place the one or more guest computing system instances in the virtualized computing system from a capacity request queue, at least: determining an initial placement for fulfilling the one or more capacity requests by assigning the one or more capacity requests to the regions based at least in part on one or more constraints for fulfilling the one or more capacity requests, the regions to which the one or more capacity requests are assigned forming assigned regions; after selecting the initial placement, determining an assignment of the one or more capacity requests to the assigned regions by, until it is determined that the placement map satisfies an objective function at least to within a threshold value, by iteratively: legalizing the placement map by reassigning at least one capacity request of the one or more capacity requests to the assigned regions based at least in part on the one or more available capacity measurements of the virtualized computing system; pinning a subset of the one or more capacity requests to the assigned regions by adding the one or more constraints between one or more capacity regions and the assigned regions; and reassigning the at least one capacity request of the one or more capacity requests to at least one other region based at least in part on the one or more constraints for fulfilling the one or more capacity requests; and after it is determined that the placement map satisfies the objective function, placing the one or more of the guest computing system instances in the virtualized computing system based at least in part on the assignment of the one or more capacity requests.