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

Cited 2 time in webofscience Cited 2 time in scopus
  • Hit : 729
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorLee, Tae-Eogko
dc.contributor.authorOh, GTko
dc.date.accessioned2008-09-22T09:34:29Z-
dc.date.available2008-09-22T09:34:29Z-
dc.date.created2012-02-06-
dc.date.created2012-02-06-
dc.date.created2012-02-06-
dc.date.issued1997-
dc.identifier.citationEUROPEAN JOURNAL OF OPERATIONAL RESEARCH, v.103, no.3, pp.584 - 594-
dc.identifier.issn0377-2217-
dc.identifier.urihttp://hdl.handle.net/10203/7396-
dc.description.abstractWe 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.-
dc.languageEnglish-
dc.language.isoen_USen
dc.publisherELSEVIER SCIENCE BV-
dc.titleThe asymptotic value-to-capacity ratio for the multi-class stochastic knapsack problem-
dc.typeArticle-
dc.identifier.wosidA1997YL12200013-
dc.identifier.scopusid2-s2.0-0031352230-
dc.type.rimsART-
dc.citation.volume103-
dc.citation.issue3-
dc.citation.beginningpage584-
dc.citation.endingpage594-
dc.citation.publicationnameEUROPEAN JOURNAL OF OPERATIONAL RESEARCH-
dc.identifier.doi10.1016/S0377-2217(96)00308-6-
dc.embargo.liftdate9999-12-31-
dc.embargo.terms9999-12-31-
dc.contributor.localauthorLee, Tae-Eog-
dc.contributor.nonIdAuthorOh, GT-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorprobabilistic programming-
dc.subject.keywordAuthorstochastic knapsack problem-
dc.subject.keywordAuthormultiple classes-
dc.subject.keywordPlusCONSTRAINT RANDOM KNAPSACKS-
dc.subject.keywordPlusNP-COMPLETE PROBLEMS-
dc.subject.keywordPlusMARTINGALE INEQUALITIES-
dc.subject.keywordPlusGROWTH-
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