A Polynomial Algorithm for the Two-Variable Integer Programming Problem
From MaRDI portal
Publication:3858024
DOI10.1145/322169.322179zbMath0423.90052MaRDI QIDQ3858024
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
computational complexity; knapsack problem; polynomial algorithm; coefficient size; feasible region decomposition; two-variable integer programming
Related Items
Lifting for the integer knapsack cover polyhedron, On polynomial kernels for sparse integer linear programs, On the exact separation of mixed integer knapsack cuts, Computing efficiently the lattice width in any dimension, Non-standard approaches to integer programming, An exact algorithm for large unbounded knapsack problems, An integral transformation for integer programming problems, A polynomial algorithm for a one machine batching problem, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, A linear algorithm for integer programming in the plane, Proportionate progress: A notion of fairness in resource allocation, An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling, Description of 2-integer continuous knapsack polyhedra, Efficient Lattice Width Computation in Arbitrary Dimension