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
- 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?)
- 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
- 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 THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
- 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
- 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)- Enumeration and unimodular equivalence of empty delta-modular simplices
- The integrality number of an integer program
- The distributions of functions related to parametric integer optimization
- FPT-algorithms for some problems related to integer programming
- On integer programming with bounded determinants
- On lattice point counting in -modular polyhedra
- FPT-algorithm for computing the width of a simplex given by a convex hull
- Enumerating integer points in polytopes with bounded subdeterminants
- On -modular integer linear problems in the canonical form and equivalent problems
- Complexity of optimizing over the integers
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)
