<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>828</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2004-12-22</completedDate>
    <publishedDate>2004-12-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Polynomial Inequalities Representing Polyhedra</title>
    <abstract language="eng">Our main result is that every $n$-dimensional polytope can be described by at most $2n-1$ polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an $n$-dimensional pointed polyhedral cone we prove the bound $2n-2$ and for arbitrary polyhedra we get a constructible representation by $2n$ polynomial inequalities.</abstract>
    <identifier type="serial">04-53</identifier>
    <identifier type="opus3-id">829</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8284</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Programming 103 (2005) 35-44</enrichment>
    <author>Hartwig Bosse</author>
    <author>Martin Grötschel</author>
    <author>Martin Henk</author>
    <series>
      <title>ZIB-Report</title>
      <number>04-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedra and polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>semi-algebraic sets</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedral combinatorics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polynomial inequalities</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stability index</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="14P10">Semialgebraic sets and related spaces</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52B55">Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/828/ZR-04-53.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/828/ZR-04-53.pdf</file>
  </doc>
  <doc>
    <id>682</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-03-27</completedDate>
    <publishedDate>2002-03-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the Representation of Polyhedra by Polynomial Inequalities</title>
    <abstract language="eng">A beautiful result of Bröcker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every $d$-dimensional polyhedron admits a representation as the set of solutions of at most $d(d+1)/2$ polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the 2- and 3-dimensional case we get the expected number $d(d+1)/2$.</abstract>
    <identifier type="serial">02-15</identifier>
    <identifier type="opus3-id">683</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6826</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete &amp; Computational Geometry 29 (2003) 485-504 under the title: "The Representation of Polyhedra by Polynomial Inequalities"</enrichment>
    <author>Martin Grötschel</author>
    <author>Martin Henk</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-15</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedra and polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>semialgebraic sets</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedral combinatorics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polynomial inequalities</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="14P10">Semialgebraic sets and related spaces</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52B55">Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/682/ZR-02-15.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/682/ZR-02-15.pdf</file>
  </doc>
  <doc>
    <id>747</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-08-13</completedDate>
    <publishedDate>2003-08-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Polynomial Inequalities Representing Polyhedra</title>
    <abstract language="eng">Our main result is that every n-dimensional polytope can be described by at most (2n-1) polynomial inequalities and, moreover, these polynomials can explicitly be constructed. For an n-dimensional pointed polyhedral cone we prove the bound 2n-2 and for arbitrary polyhedra we get a constructible representation by 2n polynomial inequalities.</abstract>
    <identifier type="serial">03-25</identifier>
    <identifier type="opus3-id">748</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7473</identifier>
    <enrichment key="SourceTitle">For a rev. vers. see ZR-04-53; the final version appeared in: Mathematical Programming 103 (2005) 35-44</enrichment>
    <author>Hartwig Bosse</author>
    <author>Martin Grötschel</author>
    <author>Martin Henk</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-25</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedra and polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>semi-algebraic sets</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polyhedral combinatorics</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polynomial inequalities</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stability index</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="14P10">Semialgebraic sets and related spaces</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52B55">Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C57">Polyhedral combinatorics, branch-and-bound, branch-and-cut</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/747/ZR-03-25.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/747/ZR-03-25.pdf</file>
  </doc>
</export-example>
