Tight complexity bounds for the two-dimensional real knapsack problem
type: Item
instance of: scholarly article
title: Tight complexity bounds for the two-dimensional real knapsack problem
zbMATH Open document ID: 0947.65065
author: Valentin E. Brimkov
author: Stephan Stoyanov Danchev
author: Mauro Leoncini
published in: Calcolo
publication date: 2000-10-22T00:00:00Z
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.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C10
zbMATH DE Number: 1330875
zbMATH Keywords: complexity bounds
zbMATH Keywords: two-dimensional knapsack problem
reviewed by: Horst Hollatz
MaRDI profile type: Publication
full work available at URL: s100920050026
OpenAlex ID: W2018488770
DOI: 10.1007/S100920050026
Recommended article: Faster approximation schemes for the two-dimensional knapsack problem
Recommended article: Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
Recommended article: On the two-dimensional knapsack problem
Recommended article: An approximation algorithm for solving unconstrained two-dimensional knapsack problems
Recommended article: On the approximability of the two-phase knapsack problem
Recommended article: An exact algorithm for general, orthogonal, two-dimensional knapsack problems
Recommended article: An approximation scheme for the two-stage, two-dimensional knapsack problem
Recommended article: Exact algorithms for the two-dimensional guillotine knapsack
Recommended article: Some computational results on real 0-1 knapsack problems
Recommended article: Approximation algorithms for a two-phase knapsack problem
description: scientific article; zbMATH DE number 1330875