Lifts for Voronoi cells of lattices
From MaRDI portal
Publication:6050227
DOI10.1007/s00454-023-00522-zzbMath1523.52015arXiv2106.04432OpenAlexW3168387142MaRDI QIDQ6050227
Stefan Weltge, Ina Seidel, Matthias Schymura
Publication date: 12 October 2023
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2106.04432
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07) Linear programming (90C05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Smallest compact formulation for the permutahedron
- On linear systems with integral valued solutions
- Using separation algorithms to generate mixed integer model reformulations
- Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus
- Expressing combinatorial optimization problems by linear programs
- Zonotopes, dicings, and Voronoi's conjecture on parallelohedra
- Geometric algorithms and combinatorial optimization.
- A characterization of root lattices
- Extension complexity and realization spaces of hypersimplices
- Combinatorial bounds on nonnegative rank and extended formulations
- A short proof that the extension complexity of the correlation polytope grows exponentially
- Small extended formulations for cyclic polytopes
- Some \(0/1\) polytopes need exponential size extended formulations
- A mean value theorem in geometry of numbers
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Lattice problems in NP ∩ coNP
- Minkowski's Convex Body Theorem and Integer Programming
- Voronoi and Delaunay cells of root lattices: classification of their faces and facets by Coxeter-Dynkin diagrams
- Disjunctive Programming
- Extension Complexity of Independent Set Polytopes
- The Matching Polytope has Exponential Extension Complexity
- On the equidistribution of Hecke points
- Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
- Regular Matroids Have Polynomial Extension Complexity
- A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices
- Lifts of Convex Sets and Cone Factorizations
- Convex and Discrete Geometry
- Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
- Linear vs. semidefinite extended formulations
- On compact representations of Voronoi cells of lattices
- Extended formulations in combinatorial optimization
