The width and integer optimization on simplices with bounded minors of the constraint matrices
From MaRDI portal
(Redirected from Publication:315480)
Abstract: In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices assuming that some minors of the constraint matrices of the simplices are bounded.
Recommendations
Cites work
- A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
- A study of the boundary graph classes for colorability problems
- Boundary classes of graphs for the dominating set problem
- Boundary properties of graphs for algorithmic graph problems
- Classes of graphs critical for the edge list-ranking problem
- Continuous sets of the boundary classes of graphs for coloring problems
- Critical hereditary graph classes: a survey
- Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
- Faster deterministic volume estimation in the oracle model via thin lattice coverings
- Handbook of global optimization
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 1254302 (Why is no real title available?)
- scientific article; zbMATH DE number 1342145 (Why is no real title available?)
- scientific article; zbMATH DE number 1405493 (Why is no real title available?)
- scientific article; zbMATH DE number 958053 (Why is no real title available?)
- scientific article; zbMATH DE number 3046578 (Why is no real title available?)
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
- NP-hard graph problems and boundary classes of graphs
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- On integer programming with bounded determinants
- On minimal complex classes of graphs
- On the complexity of integer programming
- On the maximal width of empty lattice simplices
- ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- Polynomial algorithms in linear programming
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
- The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
Cited in
(10)- FPT-algorithms for some problems related to integer programming
- The integrality number of an integer program
- On lattice point counting in -modular polyhedra
- FPT-algorithm for computing the width of a simplex given by a convex hull
- On integer programming with bounded determinants
- Enumerating integer points in polytopes with bounded subdeterminants
- The distributions of functions related to parametric integer optimization
- Enumeration and unimodular equivalence of empty delta-modular simplices
- Complexity of optimizing over the integers
- On -modular integer linear problems in the canonical form and equivalent problems
This page was built for publication: The width and integer optimization on simplices with bounded minors of the constraint matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q315480)
