A Polynomial Algorithm for the Two-Variable Integer Programming Problem

DOI10.1145/322169.322179MaRDI QIDQ3858024zbMATH OpenOpenAlexFDO

Authors 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

coefficient sizecomputational complexityfeasible region decompositionknapsack problempolynomial algorithmtwo-variable integer programming

Mathematics Subject Classification ID

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

Cited in

(14)

• 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
• On polynomial kernels for sparse integer linear programs
• Efficient lattice width computation in arbitrary dimension
• On the exact separation of mixed integer knapsack cuts
• Lifting for the integer knapsack cover polyhedron
• Computing efficiently the lattice width in any dimension
• Non-standard approaches to integer programming
• An exact algorithm for large unbounded knapsack problems

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)