Tight complexity bounds for the two-dimensional real knapsack problem

DOI10.1007/S100920050026MaRDI QIDQ1300669zbMATH OpenOpenAlexFDO

Authors Valentin E. Brimkov, Stephan Stoyanov Danchev, Mauro Leoncini

Publication date 22 October 2000

Published in Calcolo (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s100920050026

zbMATH Keywords

complexity boundstwo-dimensional knapsack problem

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Complexity and performance of numerical algorithms (65Y20) Linear programming (90C05) Integer programming (90C10)

Review text

It is proved that the complexity of the two-dimensional knapsack problem with real coefficients is given by \(\Theta(\log(b/\min(a_1,a_2))\), where \(a_1, a_2\) are the coefficients of the contraint inequality.

Recommendations

• Faster approximation schemes for the two-dimensional knapsack problem
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• On the two-dimensional knapsack problem
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• On the approximability of the two-phase knapsack problem
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• An approximation scheme for the two-stage, two-dimensional knapsack problem
• Exact algorithms for the two-dimensional guillotine knapsack
• Some computational results on real 0-1 knapsack problems
• Approximation algorithms for a two-phase knapsack problem

Cited in

(1)

• An alternative to Ben-Or's lower bound for the knapsack problem complexity

This page was built for publication: Tight complexity bounds for the two-dimensional real knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1300669)