We study the complexity of the 2-dimensional knapsack problem max{c_1 x + c_2 y : a_1 x + a_2 y <= b; x, y \in Z_+}, where c_1, c_2, a_1, a_2, b \in 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}.
Tight Complexity Bounds for the Two-Dimensional Real Knapsack
LEONCINI, MAURO
1999-01-01
Abstract
We study the complexity of the 2-dimensional knapsack problem max{c_1 x + c_2 y : a_1 x + a_2 y <= b; x, y \in Z_+}, where c_1, c_2, a_1, a_2, b \in 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}.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
