Tight complexity bounds for the two-dimensional real knapsack problem

Abstract

We study the complexity of the 2-dimensional knapsack problem max{c(1)x + c(2)y : a(1)x + a(2)y less than or equal to b, x, y is an element of Z(+)}, where c(1), c(2), a(1), a(2), b is an element of R+. The problem is defined in terms of real numbers and we study it where an integral solution is sought under a real number model of computation. We obtain a tight complexity bound Theta(log b/a(min)), where a(min) = min{a(1), a(2)}.