Enumerating integer points in polytopes with bounded subdeterminants
From MaRDI portal
Abstract: We show that one can enumerate the vertices of the convex hull of integer points in polytopes whose constraint matrices have bounded and nonzero subdeterminants, in time polynomial in the dimension and encoding size of the polytope. This extends a previous result by Artmann et al. who showed that integer linear optimization in such polytopes can be done in polynomial time.
Recommendations
- The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
- Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
- A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON
- On integer points in polyhedra
- On integer programming with bounded determinants
Cites work
- A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity \(2^{O(n\log n)}\)
- A note on non-degenerate integer programs with small sub-determinants
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- A strongly polynomial algorithm for bimodular integer linear programming
- Algebraic and geometric ideas in the theory of discrete optimization
- Complexity of integer quasiconvex polynomial optimization
- Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- Integer optimization on convex semialgebraic sets
- Integer program with bimodular matrix
- Integer Programming
- Integer Programming with a Fixed Number of Variables
- Minkowski's Convex Body Theorem and Integer Programming
- Nonlinear discrete optimization. An algorithmic theory
- On integer points in polyhedra
- On integer points in polyhedra: A lower bound
- On integer programming with bounded determinants
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- Some polyhedra related to combinatorial problems
- The Integrality Number of an Integer Program
- The width and integer optimization on simplices with bounded minors of the constraint matrices
Cited in
(19)- Enumerating extreme points of a highly degenerate polytope
- Enumerating a subset of the integer points inside a Minkowski sum
- A note on non-degenerate integer programs with small sub-determinants
- Counting integer points of flow polytopes
- Enumeration of integer points in projections of unbounded polyhedra
- Counting integer points in higher-dimensional polytopes
- On integer programming with bounded determinants
- scientific article; zbMATH DE number 5542490 (Why is no real title available?)
- Counting the Number of Integral Points in General n-Dimensional Tetrahedra and Bernoulli Polynomials
- Enumerating projections of integer points in unbounded polyhedra
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- On lattice width of lattice-free polyhedra and height of Hilbert bases
- Enumerating vertices of 0/1-polyhedra associated with 0/1-totally unimodular matrices
- Fully Bounded Polyhedral Analysis of Integers with Wrapping
- Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
- Complexity of optimizing over the integers
- Unimodular polytopes and column number bounds on polytopal totally unimodular matrices via Seymour's decomposition theorem
- On the size of integer programs with bounded non-vanishing subdeterminants
- On generic -modular integer matrices with two rows
This page was built for publication: Enumerating integer points in polytopes with bounded subdeterminants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5062109)
