Optimal compactification of a floorplan and its relation to other optimization problems: A dynamic programming approach

The paper examines an algorithm for the compactification of an arrangement of rectangles in the plane as it is used for floorplans in the automated design of electronic circuits (also called sizing of floorplans). It reformulates this problem as a multistage decision problem and shows that the algorithm is in fact the optimal solution obtained by the backward induction procedure of dynamic programming. The model allows generalizations to non-geometrical applications in scheduling and reliability.