Stochastic on-line knapsack problems

Stochastic on-line knapsack problems

0.00 Avg rating0 Votes
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: ,
Keywords: programming: probabilistic
Abstract:

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 O(log3’/2n). An ¦[(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.

Reviews

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