Efficient list-approximation techniques for floorplan area minimization

摘要

As the sizes of many IC design problems become increasingly larger, approximation has become a valuable approach for arriving at satisfactory results without incurring exorbitant computational cost. In this paper, we present several approximation techniques for solving floorplan area minimization problems. These new techniques enable us to reduce both the time and space complexities of the previously best known approximation algorithms by more than a factor of n and n{sup}2 for rectangular and L-shaped subfloorplans, respectively (where n is the number of given implementations). The improvements in the time and space complexities of such approximation techniques is critical to their applicability in floorplan area minimization algorithms. The techniques are quite general, and may be applicable to other classes of approximation problems.