QUADRATIC O 1 OPTIMIZATION AND A DECOMPOSITION APPROACH FOR THE PLACEMENT OF ELECTRONIC-CIRCUITS/

The placement problem in the layout design of electronic circuits cons ists of finding a nonoverlapping assignment of rectangular cells to po sitions on the chip so that wireability is guaranteed and certain tech nical constraints are met. This problem can be modelled as a quadratic 0/1-program subject to linear constraints. We will present a decompos ition approach to the placement problem and give results above NP-hard ness and the existence of epsilon-approximative algorithms for the inv olved optimization problems. A graph theoretic formulation of these pr oblems will enable us to develop approximative algorithms. Finally we will present details of the implementation of our approach and compare it to industrial state of the art placement routines.