Tight complexity bounds for the two-dimensional real knapsack problem (Q1300669)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Tight complexity bounds for the two-dimensional real knapsack problem |
scientific article; zbMATH DE number 1330875
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Tight complexity bounds for the two-dimensional real knapsack problem |
scientific article; zbMATH DE number 1330875 |
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
0 references
0 references
0 references
0.9034517
0 references
0.89940244
0 references
0.89905906
0 references
0.8962929
0 references
0.8944502
0 references
0.88591063
0 references
0.88336533
0 references
