On Stockmeyer's floorplan optimization technique

Studies the time complexity of L. Stockmeyer's technique (1993) to solve the floorplan area optimization problem for hierarchical floorplans of order 5. The authors develop a method of constructing bad floorplans to show that Stockmeyer's technique inherently has exponential time complexity. The special case is considered where the modules all have integer dimensions, and it is shown that this problem can be solved in pseudopolynomial time by Stockmeyer's technique. For the general case in which the dimensions are real numbers, a pseudopolynomial-time epsilon -approximation algorithm is presented for solving this problem. The last two results can also be extended to hierarchical floorplans of higher order.<
>