Complexity and approximability results for slicing floorplan designs

Vladimir G. Deineko, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

The first stage in hierarchical approaches to floorplan design determines certain topological relations between the positions of indivisible cells on a VLSI 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.
Original languageEnglish
Pages (from-to)533-539
Number of pages7
JournalEuropean journal of operational research
Volume149
Issue number3
DOIs
Publication statusPublished - 2003

Keywords

  • Approximation
  • Compaction
  • Combinatorial optimization
  • Floorplan design
  • IR-75019
  • Computational Complexity
  • VLSI design
  • Packing
  • METIS-213303
  • Cutting

Fingerprint Dive into the research topics of 'Complexity and approximability results for slicing floorplan designs'. Together they form a unique fingerprint.

  • Cite this