Enumeration and unimodular equivalence of empty delta-modular simplices

DOI10.1007/978-3-031-35305-5_8zbMATH Open1529.90052arXiv2303.01224MaRDI QIDQ6134052FDOQ6134052

Author name not available (Why is that?)

Publication date: 21 August 2023

Published in: Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Abstract: Consider a class of simplices defined by systems $Axleqb$ of linear inequalities with $Delta$-modular matrices. A matrix is called $Delta$-modular, if all its rank-order sub-determinants are bounded by $Delta$ in an absolute value. In our work we call a simplex $Delta$-modular, if it can be defined by a system $Axleqb$ with a $Delta$-modular matrix $A$. And we call a simplex empty, if it contains no points with integer coordinates. In literature, a simplex is called lattice-simplex, if all its vertices have integer coordinates. And a lattice-simplex called empty, if it contains no points with integer coordinates excluding its vertices. Recently, assuming that $Delta$ is fixed, it was shown that the number of $Delta$-modular empty simplices modulo the unimodular equivalence relation is bounded by a polynomial on dimension. We show that the analogous fact holds for the class of $Delta$-modular empty lattice-simplices. As the main result, assuming again that the value of the parameter $Delta$ is fixed, we show that all unimodular equivalence classes of simplices of the both types can be enumerated by a polynomial-time algorithm. As the secondary result, we show the existence of a polynomial-time algorithm for the problem to check the unimodular equivalence relation for a given pair of $Delta$-modular, not necessarily empty, simplices.

Full work available at URL: https://arxiv.org/abs/2303.01224

zbMATH Keywords

unimodular equivalenceenumeration algorithmlattice simplexempty simplexbounded sub-determinantsdelta-modular matrix

Mathematics Subject Classification ID

Integer programming (90C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Canonical forms, reductions, classification (15A21) Lattices and convex bodies (number-theoretic aspects) (11H06)

Cites Work

• Computing the Continuous Discretely
• Lattice Tetrahedra
• Integer Programming with a Fixed Number of Variables
• Minimal Valid Inequalities for Integer Constraints
• Title not available (Why is that?)
• Inequalities from Two Rows of a Simplex Tableau
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithms - ESA 2003
• Title not available (Why is that?)
• New bounds in some transference theorems in the geometry of numbers
• Covering minima and lattice-point-free convex bodies
• On the maximal width of empty lattice simplices
• Duality for mixed-integer convex minimization
• A Strong Dual for Conic Mixed-Integer Programs
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• Integer points in polyhedra
• On Lovász' lattice reduction and the nearest lattice point problem
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• On integer programming with bounded determinants
• The width and integer optimization on simplices with bounded minors of the constraint matrices
• Title not available (Why is that?)
• Terminal Quotient Singularities in Dimensions Three and Four
• Integer programming duality: Price functions and sensitivity analysis
• On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension
• Title not available (Why is that?)
• Short rational generating functions for lattice point problems
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Constructive characterizations of the value-function of a mixed-integer program. I
• Computing parametric rational generating functions with a primal Barvinok algorithm
• Relaxations of mixed integer sets from lattice-free polyhedra
• Integer conic function minimization based on the comparison oracle
• A polynomial algorithm for minimizing discrete convic functions in fixed dimension
• On the complexity of quasiconvex integer minimization problem
• Linear and Integer Programming vs Linear Integration and Counting
• The b-hull of an integer program
• On the width of lattice-free simplices
• Constructive characterizations of the value function of a mixed-integer program. II
• On Four-Dimensional Terminal Quotient Singularities
• Title not available (Why is that?)
• A geometric approach to cut-generating functions
• Classification of empty lattice 4-simplices of width larger than 2
• The complete classification of empty lattice 4-simplices
• Optimality certificates for convex minimization and Helly numbers
• FPT-algorithms for some problems related to integer programming
• Quotient Singularities, Integer Ratios of Factorials, and the Riemann Hypothesis
• Lattice-free simplices with lattice width \(2d - o(d)\)
• Hollow polytopes of large width
• Constructing lattice-free gradient polyhedra in dimension two
• FPT-algorithm for computing the width of a simplex given by a convex hull
• Improving the Cook et al. proximity bound given integral valued constraints
• The structure of simple sets in \(\mathbb Z^3\)
• On Lattice Width of Lattice-Free Polyhedra and Height of Hilbert Bases

This page was built for publication: Enumeration and unimodular equivalence of empty delta-modular simplices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134052)