Average-case performance of rollout algorithms for knapsack problems (Q2349849)

The authors analyze the performance of the two rollout algorithms applied to the stochastic subset sum problem and the 0-1 knapsack problem. For both problems they propose two rollout techniques: the exhaustive rollout and the consecutive rollout, using the blind-greedy algorithm as a base policy. The expected performance of the both rollout techniques is investigated from the probabilistic and asymptotic point of view. A number of properties of the blind-greedy solutions is derived. The authors prove an upper bound measuring the expectation of the difference between the total value of packed items and capacity for the subset sum problem. The authors also prove a lower bound on the expectation of the difference between total profit of the rollout algorithm and the blind-greedy algorithm for the 0-1 knapsack problem. The significant gain in expected performance of the rollout algorithm in comparison with the blind-greedy algorithm is shown.