Area minimization for floorplans

In this paper we study the area minimization problem in floorplanning (also known as the floorplan sizing problem). For a given floorplan, the problem is to select a layout alternative for each subcircuit on a chip so as to minimize the chip area. Two area minimization methods for general floorplans are proposed. Both methods can be viewed as generalizations of the classical algorithm for slicing floorplans of Otten (1982) and Stockmeyer (1983) in the sense that they reduce naturally to their algorithm for slicing floorplans. Compared with the branch-and-bound algorithm of Wimer et al (1989), which does not have a nontrivial performance bound, our methods are provably better than an exhaustive method for all the examples we examined