A Polynomial Algorithm for the Two-Variable Integer Programming Problem

DOI10.1145/322169.322179zbMATH Open0423.90052OpenAlexW2112960677MaRDI QIDQ3858024FDOQ3858024

R. Kannan

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322169.322179

zbMATH Keywords

computational complexityknapsack problempolynomial algorithmcoefficient sizefeasible region decompositiontwo-variable integer programming

Mathematics Subject Classification ID

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

Cited In (14)

• Lifting for the integer knapsack cover polyhedron
• Non-standard approaches to integer programming
• On polynomial kernels for sparse integer linear programs
• A linear algorithm for integer programming in the plane
• An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling
• Efficient Lattice Width Computation in Arbitrary Dimension
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• An integral transformation for integer programming problems
• Proportionate progress: A notion of fairness in resource allocation
• Description of 2-integer continuous knapsack polyhedra
• On the exact separation of mixed integer knapsack cuts
• An exact algorithm for large unbounded knapsack problems
• Computing efficiently the lattice width in any dimension
• A polynomial algorithm for a one machine batching problem

This page was built for publication: A Polynomial Algorithm for the Two-Variable Integer Programming Problem

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