Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits

Jünger, Michael and Martin, Alexander and Reinelt, Gerhard and Weismantel, Robert (1994) Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.
Published in: Mathematical Programming Vol. 63 (1-3). pp. 257-279.

Abstract

The placement problem in the layout design of electronic circuits consists of finding a non-overlapping assignment of rectangular cells to positions on the chip so that 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 NP-hardness and the existence of varepsilon-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.


Actions:
Full text not available from this repository.
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: [error in script] 33 (Google Scholar) | [error in script]
Uncontrolled Keywords: [error in script]
Subjects:
Uncontrolled Keywords: epsilon-approximative algorithms, layout design of electronic circuits, NP-hardness, quadratic 0/1-optimization, VLSI design
Subjects: UNSPECIFIED
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 11:13
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Prof. Dr. Michael Jünger
Date Deposited: 27 Jun 2003 00:00
Last Modified: 19 Jan 2012 11:13
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/102