Article ID: | iaor1997695 |
Country: | Netherlands |
Volume: | 68 |
Issue: | 1 |
Start Page Number: | 73 |
End Page Number: | 104 |
Publication Date: | Jan 1995 |
Journal: | Mathematical Programming (Series A) |
Authors: | Vercellis C., Marchetti-Spaccamela A. |
Keywords: | programming: probabilistic |
Different classes of on-line algorithms are developed and analyzed for the solution of {0,1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value is