The width and integer optimization on simplices with bounded minors of the constraint matrices

DOI10.1007/S11590-016-1048-YzbMATH Open1377.90059arXiv1710.00328OpenAlexW2434330280MaRDI QIDQ315480FDOQ315480

A. Y. Chirkov, Dmitriy V. Gribanov

Publication date: 21 September 2016

Published in: Optimization Letters (Search for Journal in Brave)

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.

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

Recommendations

• FPT-algorithm for computing the width of a simplex given by a convex hull
• On integer programming with bounded determinants
• On the width of lattice-free simplices
• On Integer Programming and the Branch-Width of the Constraint Matrix
• Integer Polynomial Optimization in Fixed Dimension

zbMATH Keywords

integer programmingpolytopeefficient algorithmwidthflatness theoremmatrix minorsunimodular decomposition

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

• Handbook of global optimization
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Boundary classes of graphs for the dominating set problem
• NP-hard graph problems and boundary classes of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial algorithms in linear programming
• ON THE RELATION BETWEEN INTEGER AND NONINTEGER SOLUTIONS TO LINEAR PROGRAMS
• Boundary properties of graphs for algorithmic graph problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Title not available (Why is that?)
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• On the maximal width of empty lattice simplices
• The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\). II: Application of \(K\)-convexity
• Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
• On integer programming with bounded determinants
• On the complexity of integer programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Critical hereditary graph classes: a survey
• A study of the boundary graph classes for colorability problems
• Classes of graphs critical for the edge list-ranking problem
• The Flatness Theorem for Some Class of Polytopes and Searching an Integer Point
• Faster Deterministic Volume Estimation in the Oracle Model via Thin Lattice Coverings
• Title not available (Why is that?)

Cited In (9)

• The integrality number of an integer program
• Enumerating Integer Points in Polytopes with Bounded Subdeterminants
• FPT-algorithms for some problems related to integer programming
• On lattice point counting in \(\varDelta\)-modular polyhedra
• FPT-algorithm for computing the width of a simplex given by a convex hull
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• The Distributions of Functions Related to Parametric Integer Optimization
• Complexity of optimizing over the integers
• Enumeration and unimodular equivalence of empty delta-modular simplices

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)