A Polynomial Algorithm for the Two-Variable Integer Programming Problem

DOI10.1145/322169.322179zbMath0423.90052OpenAlexW2112960677MaRDI QIDQ3858024

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

Related Items

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

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