Publication | Open Access
A Polynomial-Time Algorithm for the Knapsack Problem with Two Variables
67
Citations
4
References
1976
Year
Mathematical ProgrammingEngineeringInteger OptimizationOptimization ProblemKnapsack ProblemGeneral Knapsack ProblemCombinatorial ProblemLogisticsComputational ComplexityComputer ScienceDiscrete MathematicsLinear ProgrammingCombinatorial OptimizationDiscrete OptimizationPolynomial TimeInteger ProgrammingOperations Research
The general knapsack problem is known to be NP-complete. In this paper a very special knapsack problem ia studied, namely, one with only two variables. A polynomial-time algorithm is presented and analyzed. However, it remains an open problem that for any fixed n > 2, the knapsack problem with n variables can be solved in polynomial time.
| Year | Citations | |
|---|---|---|
Page 1
Page 1