Back to Search
Start Over
d-Dimensional Knapsack in the Streaming Model.
- Source :
- Algorithms - ESA 2009; 2009, p468-479, 12p
- Publication Year :
- 2009
-
Abstract
- We study the d-dimensional knapsack problem in the data streaming model. The knapsack is modelled as a d-dimensional integer vector of capacities. For simplicity, we assume that the input is scaled such that all capacities are 1. There is an input stream of n items, each item is modelled as a d-dimensional integer column of non-negative integer weights and a scalar profit. The input instance has to be processed in an online fashion using sub-linear space. After the items have arrived, an approximation for the cost of an optimal solution as well as a template for an approximate solution is output. Our algorithm achieves an approximation ratio ]> using space O(2<superscript>O(d)</superscript> ·log<superscript>d + 1</superscript>d ·log<superscript>d + 1</superscript> ∆·logn) bits, where ]> , ∆ ≥ 2 is the set of possible profits and weights in any dimension. We also show that any data streaming algorithm for the t(t − 1)-dimensional knapsack problem that uses space ]> cannot achieve an approximation ratio that is better than 1/t. Thus, even using space ∆<superscript>ν</superscript>, for ν< 1/2, i.e. space polynomial in ∆, will not help to break the ]> barrier in the approximation ratio. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642041273
- Database :
- Complementary Index
- Journal :
- Algorithms - ESA 2009
- Publication Type :
- Book
- Accession number :
- 76842291
- Full Text :
- https://doi.org/10.1007/978-3-642-04128-0_42