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

integer programminglinear programmingrestricted determinants

Mathematics Subject Classification ID

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

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

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

Cited in

(25)

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

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)