Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.
Appeared in: Mathematical Programming vol. 63 (1994) pp. 257-279
| SC 92-10 | M. Jünger, Alexander Martin, G. Reinelt, Robert Weismantel
Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits. Appeared in: Mathematical Programming vol. 63 (1994) pp. 257-279 | |
Abstract: The placement in the layout design of
electronic circiuts consists of finding a non- overlapping
assignment of rectangular cells to positions on the chip so
what wireability is guaranteed and certain technical
constraints are met.This problem can be modelled as a
quadratic 0/1- program subject to linear constraints. We
will present a decomposition approach to the placement
problem and give results about 
-hardness and the
existence of 
-approximative algorithms for the
involved optimization problems. A graphtheoretic formulation
of these problems 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.
Keywords:
Quadratic 0/1 optimization, Computational Complexity,
VLSI-Design.
Keywords: quadratic 0/1 optimization,
computational complexity,
VLSI-Design