The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem

The asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem

0.00 Avg rating0 Votes
Article ID: iaor19992038
Country: Netherlands
Volume: 103
Issue: 3
Start Page Number: 584
End Page Number: 594
Publication Date: Dec 1997
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer
Abstract:

We consider a stochastic knapsack problem that packs multiple classes of random items. The pairs of profit and resource requirement for items of the same class are independent and identically distributed. However, such pairs for different classes of items are independent but not necessarily identically distributed. We investigate convergence and the asymptotic value of the ratio of the knapsack value function to the capacity when the capacity increases. We consider two growth models for the multi-class stochastic knapsack problem, one where the number of available items grows proportionally to the capacity and the other one where the available items are sampled until their total resource requirement does not exceed the capacity. By extending the results of Meanti et al. on a single class of random items, we show that for each growth model, the ratio converges almost surely to a computable constant. For special cases where resource requirements or profit coefficients are deterministic, we present simple interpretations on the asymptotic values. Finally, we present an exponential order upper bound on the tail probability of the ratio.

Reviews

Required fields are marked *. Your email address will not be published.