Tight complexity bounds for the two-dimensional real knapsack problem (Q1300669)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Tight complexity bounds for the two-dimensional real knapsack problem |
scientific article |
Statements
Tight complexity bounds for the two-dimensional real knapsack problem (English)
0 references
22 October 2000
0 references
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.
0 references
complexity bounds
0 references
two-dimensional knapsack problem
0 references
