<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>80</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1992-04-09</completedDate>
    <publishedDate>1992-04-09</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Quadratic 0/1 Optimization and a Decomposition Approach for the Placement of Electronic Circuits.</title>
    <abstract language="eng">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 $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. {\bf Keywords:} Quadratic 0/1 optimization, Computational Complexity, VLSI-Design.</abstract>
    <identifier type="serial">SC-92-10</identifier>
    <identifier type="opus3-id">79</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-803</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Programming vol. 63 (1994) pp. 257-279</enrichment>
    <author>Michael Jünger</author>
    <author>Alexander Martin</author>
    <author>Gerhard Reinelt</author>
    <author>Robert Weismantel</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-92-10</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>quadratic 0/1 optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>computational complexity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>VLSI-Design</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/80/SC-92-10.pdf</file>
  </doc>
</export-example>
