





















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 / \log d)}$ 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(d \log d)$ facets, respectively. We obtain similar results for spectrahedral lifts.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。