Complexity and approximability results for slicing floorplan designs

Complexity and approximability results for slicing floorplan designs

0.00 Avg rating0 Votes
Article ID: iaor20042917
Country: Netherlands
Volume: 149
Issue: 3
Start Page Number: 533
End Page Number: 539
Publication Date: Sep 2003
Journal: European Journal of Operational Research
Authors: ,
Keywords: electronics industry
Abstract:

The first stage in hierarchical approaches to floorplan design determines certain topological relations between the positions of indivisible cells on a very large scale integration chip. Various optimizations are then performed on this initial layout to minimize certain cost measures such as the chip area. We consider optimization problems in fixing the orientations of the cells and simultaneously fixing the directions of the cuts that are specified by a given slicing tree; the goal is to minimize the area of the chip. We prove that these problems are NP-hard in the ordinary sense, and we describe a pseudo-polynomial time algorithm for them. We also present fully polynomial time approximation schemes for these problems.

Reviews

Required fields are marked *. Your email address will not be published.