Average-case performance of rollout algorithms for knapsack problems. (English) Zbl 1330.90063
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.
Reviewer: Svetlana A. Kravchenko (Minsk)
MSC:
| 90C15 | Stochastic programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C39 | Dynamic programming |
| 90C27 | Combinatorial optimization |
References:
| [1] | Bertsekas, D.P., Tsitsiklis, J., Wu, C.: Rollout algorithms for combinatorial optimization. J. Heuristics 3, 245-262 (1997) · Zbl 1071.90571 · doi:10.1023/A:1009635226865 |
| [2] | Bertsekas, D.P., Castanon, D.A.: Rollout algorithms for stochastic scheduling problems. J. Heuristics 5, 89-108 (1999) · Zbl 0997.90037 · doi:10.1023/A:1009634810396 |
| [3] | Bertsekas, D.P.: Dynamic Programming and Optimal Control, 3rd edn. Athena Scientific, Belmont, MA (2007) · Zbl 1209.90343 |
| [4] | Bertazzi, L.: Minimum and worst-case performance ratios of rollout algorithms. J. Optim. Theory Appl. 152, 378-393 (2012) · Zbl 1237.90246 · doi:10.1007/s10957-011-9902-7 |
| [5] | Borgwardt, K., Tremel, B.: The average quality of greedy-algorithms for the subset-sum-maximization problem. Math. Methods Oper. Res. 35, 113-149 (1991) · Zbl 0729.90063 · doi:10.1007/BF02331572 |
| [6] | Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004) · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7 |
| [7] | Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990) · Zbl 0708.68002 |
| [8] | Tesauro, G., Galperin, G.R.: On-line policy improvement using monte-carlo search. Adv. Neural Inf. Process. Syst. 9, 1068-1074 (1997) |
| [9] | Secomandi, N.: A rollout policy for the vehicle routing problem with stochastic demands. Oper. Res. 49, 796-802 (2001) · Zbl 1163.90373 · doi:10.1287/opre.49.5.796.10608 |
| [10] | Tu, F., Pattipati, K.: Rollout strategies for sequential fault diagnosis. In: AUTOTESTCON Proceedings, pp. 269-295. IEEE (2002) · Zbl 1163.90373 |
| [11] | Li, Y., Krakow, L.W., Chong, E.K.P., Groom, K.N.: Approximate stochastic dynamic programming for sensor scheduling to track multiple targets. Digit. Signal Process. 19, 978-989 (2009) · doi:10.1016/j.dsp.2007.05.004 |
| [12] | Martello, S., Toth, P.: Worst-case analysis of greedy algorithms for the subset-sum problem. Math. Program. 28, 198-205 (1984) · Zbl 0527.90072 · doi:10.1007/BF02612360 |
| [13] | D’Atri, G., Puech, C.: Probabilistic analysis of the subset-sum problem. Discret. Appl. Math. 4, 329-334 (1982) · Zbl 0493.90066 · doi:10.1016/0166-218X(82)90055-5 |
| [14] | Pferschy, U.: Stochastic analysis of greedy algorithms for the subset sum problem. Cent. Eur. J. Oper. Res. 7, 53-70 (1999) · Zbl 0941.90064 |
| [15] | Szkatula, K., Libura, M.: Probabilistic analysis of simple algorithms for binary knapsack problem. Control Cybern. 12, 147-157 (1983) · Zbl 0551.90063 |
| [16] | Szkatula, K., Libura, M.: On probabilistic properties of greedy-like algorithms for the binary knapsack problem. In: Proceedings of Advanced School on Stochastics in Combinatorial Optimization pp. 233-254 (1987) · Zbl 0647.90061 |
| [17] | Diubin, G., Korbut, A.: The average behaviour of greedy algorithms for the knapsack problem: general distributions. Math. Methods Oper. Res. 57, 449-479 (2003) · Zbl 1175.90328 |
| [18] | Calvin, J.M., Leung, J.Y.T.: Average-case analysis of a greedy algorithm for the 0/1 knapsack problem. Oper. Res. Lett. 31, 202-210 (2003) · Zbl 1064.90026 · doi:10.1016/S0167-6377(02)00222-5 |
| [19] | Dean, B.C., Goemans, M.X., Vondrdk, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 208-217. IEEE (2004) · Zbl 1071.90571 |
| [20] | Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 179-188. Society for Industrial and Applied Mathematics (1995) · Zbl 0847.90103 |
| [21] | Beier, R., Vöcking, B.: Random knapsack in expected polynomial time. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 232-241. ACM (2003) · Zbl 1192.90157 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
