Lower time bounds for integer programming with two variables

DOI10.1016/0020-0190(85)90042-0MaRDI QIDQ1072938zbMATH OpenOpenAlexFDO

Authors Clemens Lautemann, Friedhelm Meyer auf der Heide

Publication date 1985

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(85)90042-0

zbMATH Keywords

recognition problempolynomial algorithmfloor functionalgebraic computation treecomputation with polynomial orderlower time bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10)

Recommendations

• A linear algorithm for integer programming in the plane
• Algorithms and Computation
• scientific article; zbMATH DE number 1757949
• Integer programming with 2-variable equations and 1-variable inequalities
• A Fast Algorithm for the Two-Variable Integer Programming Problem

Cites work

• scientific article; zbMATH DE number 3537796 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A lower time bound for the knapsack problem on random access machines
• Integer programming and cryptography

Cited in

(11)

• The computational complexity of integer programming with alternations
• A linear algorithm for integer programming in the plane
• On the limits of computations with the floor function
• scientific article; zbMATH DE number 1405787 (Why is no real title available?)
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• scientific article; zbMATH DE number 1757949 (Why is no real title available?)
• Integer programming in an algebraic computation model
• The computational complexity of integer programming with alternations
• Fast exponentiation using the truncation operation
• 3-valued problem and reduction of some integer programming problems
• Algorithms and Computation

This page was built for publication: Lower time bounds for integer programming with two variables

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