One embodiment of the present invention provides a system that determines a feasible cell placement for an integrated circuit design. During operation, the system receives an input cell placement, which is typically determined using a quadratic placement technique. Next, the system receives a set of regions within the integrated circuit design. Each region has a capacity constraint which specifies an upper limit on the total cell area that can be placed within the region. The system then generates a bi-partite graph which comprises instance vertices, region vertices, and edges. An instance vertex is associated with a cell instance, a region vertex is associated with a region, and each edge is incident on an instance vertex and a region vertex. Each edge is assigned a cost that indicates the cost of placing the associated cell instance in the associated region. Next, the system associates edges with shadow edges. Note that an edge and an associated shadow edge are incident to the same instance vertex. The system then ranks the edges using the costs of the shadow edges. Next, the system selects a set of edges using the edge rankings. Finally, the system determines the feasible cell placement using the set of edges.