A Bound on Solutions of Linear Integer Equalities and Inequalities

DOI10.2307/2042554zbMath0397.90071OpenAlexW4246410616MaRDI QIDQ4181607

Joachim von zur Gathen, Malte Sieveking

Publication date: 1978

Full work available at URL: https://doi.org/10.2307/2042554

zbMATH Keywords

InequalitiesBound on SolutionsLinear Integer EqualitiesMatrices of Integers

Mathematics Subject Classification ID

Integer programming (90C10) Inequalities and extremum problems involving convexity in convex geometry (52A40) Linear Diophantine equations (11D04)

Related Items (38)

Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem ⋮ Pisot unit generators in number fields ⋮ On box totally dual integral polyhedra ⋮ Complexity of Subcases of Presburger Arithmetic ⋮ Minimal solutions of linear diophantine systems : bounds and algorithms ⋮ The complexity of the word problem for abelian l-groups ⋮ NP satisfiability for arrays as powers ⋮ Completeness results for conflict-free vector replacement systems ⋮ Synthesis of inhibitor-reset Petri nets: algorithmic and complexity issues ⋮ Subclasses of Presburger arithmetic and the polynomial-time hierarchy ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction ⋮ Emptiness problems for integer circuits ⋮ The computational complexity of knot genus in a fixed 3‐manifold ⋮ On Presburger arithmetic extended with non-unary counting quantifiers ⋮ Knapsack in graph groups ⋮ A polynomial algorithm for solving systems of two linear diophantine equations ⋮ Unnamed Item ⋮ The complexity of Presburger arithmetic with bounded quantifier alternation depth ⋮ Sensitivity theorems in integer linear programming ⋮ Exploiting a hypergraph model for finding Golomb rulers ⋮ Weak quantifier elimination for the full linear theory of the integers ⋮ Mixed-integer quadratic programming is in NP ⋮ Verification of parametric concurrent systems with prioritised FIFO resource management ⋮ Normal and sinkless Petri nets ⋮ Unnamed Item ⋮ Solving word equations ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ The complexity of almost linear diophantine problems ⋮ On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations ⋮ A complete and terminating approach to linear integer solving ⋮ On Affine Reachability Problems ⋮ Exact Augmented Lagrangian Duality for Mixed Integer Quadratic Programming ⋮ The existential theory of equations with rational constraints in free groups is PSPACE-complete ⋮ A Sharp Bound for Solutions of Linear Diophantine Equations ⋮ Variable metric relaxation methods, part II: The ellipsoid method ⋮ Modelization of deterministic rational relations ⋮ Small solutions of linear diophantine equations

Cites Work

• Komplexität von Entscheidungsproblemen. Ein Seminar
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• A Sharp Bound for Positive Solutions of Homogeneous Linear Diophantine Equations
• Unnamed Item

This page was built for publication: A Bound on Solutions of Linear Integer Equalities and Inequalities