<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>34149</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>845</pageFirst>
    <pageLast>865</pageLast>
    <pageNumber/>
    <edition/>
    <issue>3</issue>
    <volume>70</volume>
    <type>articlenr</type>
    <publisherName>Springer US</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2023-10-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Lifts for Voronoi cells of lattices</title>
    <abstract language="eng">Many polytopes arising in polyhedral combinatorics are linear projections of higher-dimensional polytopes with significantly fewer facets. Such lifts may yield compressed representations of polytopes, which are typically used to construct small-size linear programs. Motivated by algorithmic implications for the closest vector problem, we study lifts of Voronoi cells of lattices. We construct an explicit d -dimensional lattice such that every lift of the respective Voronoi cell has 2Ω(d/logd)facets. On the positive side, we show that Voronoi cells of d -dimensional root lattices and their dual lattices have lifts with O(d)and O(dlogd)facets, respectively. We obtain similar results for spectrahedral lifts.</abstract>
    <parentTitle language="eng">Discrete &amp; Computational Geometry</parentTitle>
    <identifier type="issn">0179-5376</identifier>
    <identifier type="issn">1432-0444</identifier>
    <identifier type="doi">10.1007/s00454-023-00522-z</identifier>
    <enrichment key="opus.import.date">2024-10-04T07:00:51+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">deepgreen</enrichment>
    <enrichment key="opus.import.file">attachment; filename=deposit.zip</enrichment>
    <enrichment key="opus.import.checksum">df6b123c63e5d0c1e5e1e0f591693fa9</enrichment>
    <enrichment key="Publikationsweg">Open Access</enrichment>
    <enrichment key="BTU">an der BTU erstellt / created at BTU</enrichment>
    <author>
      <firstName>Matthias</firstName>
      <lastName>Schymura</lastName>
    </author>
    <author>
      <firstName>Ina</firstName>
      <lastName>Seidel</lastName>
    </author>
    <author>
      <firstName>Stefan</firstName>
      <lastName>Weltge</lastName>
    </author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Lattices</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Voronoi cells</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Extended formulations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>52B05</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>52B12</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>90C05</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>52C07</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mathematical Sciences</value>
    </subject>
    <collection role="institutes" number="1302">FG Algorithmische Mathematik</collection>
    <collection role="Import" number="import">Import</collection>
  </doc>
</export-example>
