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

Cited 2 time in webofscience Cited 2 time in scopus
  • Hit : 650
  • Download : 0
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 upperbound on the tail probability of the ratio. (C) 1997 Elsevier Science B.V.
Publisher
ELSEVIER SCIENCE BV
Issue Date
1997
Language
English
Article Type
Article
Citation

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, v.103, no.3, pp.584 - 594

ISSN
0377-2217
DOI
10.1016/S0377-2217(96)00308-6
URI
http://hdl.handle.net/10203/7396
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 2 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0