A Polynomial Algorithm for the Two-Variable Integer Programming Problem

DOI10.1145/322169.322179MaRDI QIDQ3858024zbMATHOpenAlexFDO

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

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)

• On polynomial kernels for sparse integer linear programs
• Proportionate progress: A notion of fairness in resource allocation
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• An integral transformation for integer programming problems
• An algorithm reminiscent of Euclidean-gcd for computing a function related to pinwheel scheduling
• On the exact separation of mixed integer knapsack cuts
• A polynomial algorithm for a one machine batching problem
• Efficient lattice width computation in arbitrary dimension
• Lifting for the integer knapsack cover polyhedron
• Description of 2-integer continuous knapsack polyhedra
• A linear algorithm for integer programming in the plane
• 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)