A note on non-degenerate integer programs with small sub-determinants

DOI10.1016/J.ORL.2016.07.004MaRDI QIDQ1755835zbMATH OpenOpenAlexFDO

Authors S. Artmann, Robert Weismantel, Friedrich Eisenbrand, Christoph Glanzer, Timm Oertel, Santosh S. Vempala

Publication date 11 January 2019

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

linear programminginteger programmingrestricted determinants

Mathematics Subject Classification ID

Dynamic programming (90C39) Integer programming (90C10)

Abstract: The intention of this note is two-fold. First, we study integer optimization problems in standard form defined by $Ainmathbb{Z}^{mimesn}$ and present an algorithm to solve such problems in polynomial-time provided that both the largest absolute value of an entry in $A$ and $m$ are constant. Then, this is applied to solve integer programs in inequality form in polynomial-time, where the absolute values of all maximal sub-determinants of $A$ lie between $1$ and a constant.

Recommendations

• A strongly polynomial algorithm for bimodular integer linear programming
• Integer Polynomial Optimization in Fixed Dimension
• Fast integer programming in fixed dimension
• On integer programming with bounded determinants
• Enumerating integer points in polytopes with bounded subdeterminants

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3537149 (Why is no real title available?)
• Geometric algorithms and combinatorial optimization.
• Integer Programming with a Fixed Number of Variables
• Integer program with bimodular matrix
• On the complexity of integer programming
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm

Cited in

(19)

• The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
• Notes on \(\{a,b,c\}\)-modular matrices
• The integrality number of an integer program
• On the Column Number and Forbidden Submatrices for \(\Delta\)-Modular Matrices
• The complexity of some graph problems with bounded minors of their constraint matrices
• Advances on strictly \(\varDelta \)-modular IPs
• FPT-algorithms for some problems related to integer programming
• Subdeterminants and concave integer quadratic programming
• On lattice width of lattice-free polyhedra and height of Hilbert bases
• On lattice point counting in \(\varDelta\)-modular polyhedra
• The Integrality Number of an Integer Program
• FPT-algorithm for computing the width of a simplex given by a convex hull
• On the recognition of \(\{a,b,c\}\)-modular matrices
• Enumerating integer points in polytopes with bounded subdeterminants
• On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
• On the number of distinct rows of a matrix with bounded subdeterminants
• Complexity of optimizing over the integers
• 2-modular matrices
• The computational complexity of three graph problems for instances with bounded minors of constraint matrices

This page was built for publication: A note on non-degenerate integer programs with small sub-determinants

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