A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables

DOI10.1145/321921.321936zbMath0345.90048OpenAlexW2061031797WikidataQ94974067 ScholiaQ94974067MaRDI QIDQ4114964

No author found.

Publication date: 1976

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10)

Related Items

Exact Solution of Systems of Linear Equations with Iterative Methods, Intersection cuts for single row corner relaxations, On the effectivity of gradient methods for cutting stock problems, Lifted Euclidean inequalities for the integer single node flow set with upper bounds, A two-dimensional strip cutting problem with sequencing constraint, Cascading knapsack inequalities: reformulation of a crude oil distribution problem, Lifting two-integer knapsack inequalities, 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 finite-capacity production scheduling procedure for a Belgian steel company, A polynomial algorithm for a one machine batching problem, Non-standard approaches to integer programming, Unbounded knapsack problems with arithmetic weight sequences, Analysis of upper bounds for the pallet loading problem, A linear algorithm for integer programming in the plane, An algorithm for the 0/1 Knapsack problem, Description of 2-integer continuous knapsack polyhedra, An upper bound for the zero-one knapsack problem and a branch and bound algorithm, Efficient Lattice Width Computation in Arbitrary Dimension, Polyhedral description of the integer single node flow set with constant bounds, An integral transformation for integer programming problems