A Bound on Solutions of Linear Integer Equalities and Inequalities

DOI10.2307/2042554MaRDI QIDQ4181607zbMATH OpenOpenAlexFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3323651 (Why is no real title available?)
• A Sharp Bound for Positive Solutions of Homogeneous Linear Diophantine Equations
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Komplexität von Entscheidungsproblemen. Ein Seminar

Cited in

(39)

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

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

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