<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>684</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-04-08</completedDate>
    <publishedDate>2002-04-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">TOPCOM: Triangulations of Point Configurations and Oriented Matroids</title>
    <abstract language="eng">TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed.</abstract>
    <identifier type="serial">02-17</identifier>
    <identifier type="opus3-id">685</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6849</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Software - ICMS 2002 (Cohen, Arjeh M. and Gao, Xiao-Shan and Takayama, Nobuki, eds.) World Scientific (2002) 330-340</enrichment>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>point configuration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>oriented matroid</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chirotope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>circuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cocircuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>symmetry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>TOPCOM</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="msc" number="52C35">Arrangements of points, flats, hyperplanes [See also 32S22]</collection>
    <collection role="msc" number="52C40">Oriented matroids</collection>
    <collection role="msc" number="52C45">Combinatorial complexity of geometric structures [See also 68U05]</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/684/ZR-02-17.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/684/ZR-02-17.pdf</file>
  </doc>
  <doc>
    <id>764</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2003-12-05</completedDate>
    <publishedDate>2003-12-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Potential of Relaying in Cellular Networks</title>
    <abstract language="eng">Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\% on average for concrete example networks are achievable.</abstract>
    <identifier type="serial">03-42</identifier>
    <identifier type="opus3-id">765</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7641</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of INOC 2003, Evry-Paris, France, (2003) 237-242</enrichment>
    <author>Hans-Florian Geerdes</author>
    <author>Holger Karl</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-42</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Wireless ad hoc networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Resource Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Operation Research</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network Performance</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="68M12">Network protocols</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/764/ZR-03-42.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/764/ZR-03-42.pdf</file>
  </doc>
  <doc>
    <id>765</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2003-12-05</completedDate>
    <publishedDate>2003-12-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Assessing Capacity Improvements by Relaying in Cellular Networks</title>
    <abstract language="eng">Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\% on the average.</abstract>
    <identifier type="serial">03-43</identifier>
    <identifier type="opus3-id">766</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7651</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of the Int. Conf. on Opearations Research 2003, Heidelberg, Germany</enrichment>
    <author>Hans-Florian Geerdes</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Wireless ad hoc networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Resource Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Integer Programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Scheduling</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Operation Research</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network Performance</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="68M12">Network protocols</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C11">Mixed integer programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/765/ZR-03-43.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/765/ZR-03-43.pdf</file>
  </doc>
  <doc>
    <id>669</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-01-15</completedDate>
    <publishedDate>2002-01-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Computing Triangulations Using Oriented Matroids</title>
    <abstract language="eng">Oriented matroids are combinatorial structures that encode the combinatorics of point configurations. The set of all triangulations of a point configuration depends only on its oriented matroid. We survey the most important ingredients necessary to exploit oriented matroids as a data structure for computing all triangulations of a point configuration, and report on experience with an implementation of these concepts in the software package TOPCOM. Next, we briefly overview the construction and an application of the secondary polytope of a point configuration, and calculate some examples illustrating how our tools were integrated into the {\sc polymake} framework.</abstract>
    <identifier type="serial">02-02</identifier>
    <identifier type="opus3-id">670</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6692</identifier>
    <enrichment key="SourceTitle">Appeared in: Algebra, Geometry and Software Systems (Joswig, Michael and Takayama, Nobuki, eds.) Springer (2003) 49-76</enrichment>
    <author>Julian Pfeifle</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-02</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>oriented matroid</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chirotope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>circuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cocircuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>symmetry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>regular</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>secondary polytope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>hypergeometric function</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="msc" number="52C35">Arrangements of points, flats, hyperplanes [See also 32S22]</collection>
    <collection role="msc" number="52C40">Oriented matroids</collection>
    <collection role="msc" number="52C45">Combinatorial complexity of geometric structures [See also 68U05]</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/669/ZR-02-02.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/669/ZR-02-02.pdf</file>
  </doc>
  <doc>
    <id>678</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-02-28</completedDate>
    <publishedDate>2002-02-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Perfectness is an Elusive Graph Property</title>
    <abstract language="eng">A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.</abstract>
    <identifier type="serial">02-11</identifier>
    <identifier type="opus3-id">679</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6787</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM Journal on Computing 34 (2004) 109-117</enrichment>
    <author>Stefan Hougardy</author>
    <author>Annegret Wagler</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-11</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>perfect graph</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elusive graph property</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="05C17">Perfect graphs</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/678/ZR-02-11.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/678/ZR-02-11.pdf</file>
  </doc>
  <doc>
    <id>923</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-06-01</completedDate>
    <publishedDate>2006-06-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Mathematical Methods for Physical Layout of Printed Circuit Boards: An Overview</title>
    <abstract language="eng">This article surveys mathematical models and methods used for physical PCB layout, i.e., component placement and wire routing. The main concepts are briefly described together with relevant references.</abstract>
    <identifier type="serial">06-29</identifier>
    <identifier type="opus3-id">923</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9231</identifier>
    <enrichment key="SourceTitle">Appeared in: OR Spectrum 30 (2008), Nr. 3, 453–468. DOI 10.1007/s00291-007-0080-9</enrichment>
    <author>Nadine Abboud</author>
    <author>Martin Grötschel</author>
    <author>Thorsten Koch</author>
    <series>
      <title>ZIB-Report</title>
      <number>06-29</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>PCB Design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>placement</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>routing</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/923/ZR-06-29.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/923/ZR-06-29.ps</file>
  </doc>
</export-example>
