×

Learning-augmented algorithms for online subset sum. (English) Zbl 07762786

Summary: As one of Karp’s 21 NP-complete problems, the subset sum problem, as well as its generalization, has been well studied. Among the rich literature, there is little work on the online version, where items arrive over list and irrevocable decisions on packing them or not must be made immediately. Under the online setting, no deterministic algorithms are competitive, while for randomized algorithms the best competitive ratio is 1/2. It is thus of great interest to improve the performance bounds for both deterministic and randomized algorithms, assuming predicted information is available in the learning-augmented model. Along this line, we revisit online subset sum by showing that, with learnable predictions, there exist learning-augmented algorithms to break through the worst-case bounds on competitive ratio. The theoretical results are also experimentally verified, where we come up with a new idea in designing experiments. Namely, we design neural networks to serve as adversaries, verifying the robustness of online algorithms. Under this framework, several networks are trained to select adversarial instances and the results show that our algorithms are competitive and robust.

MSC:

68W01 General topics in the theory of algorithms

Software:

Knapsack
Full Text: DOI

References:

[1] Anand, K., Ge, R., Panigrahi, D.: Customizing ML predictions for online algorithms. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, vol. 119, pp. 303-313. PMLR (2020). http://proceedings.mlr.press/v119/anand20a.html
[2] Antoniadis, A., Coester, C., Eliás, M., Polak, A., Simon, B.: Online metric algorithms with untrusted predictions. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, vol. 119, pp. 345-355. PMLR (2020). http://proceedings.mlr.press/v119/antoniadis20a.html · Zbl 07753170
[3] Antoniadis, A., Gouleakis, T., Kleer, P., Kolev, P.: Secretary and online matching problems with machine learned advice. In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/5a378f8490c8d6af8647a753812f6e31-Abstract.html · Zbl 07705149
[4] Bamas, É., Maggiori, A., Rohwedder, L., Svensson, O.: Learning augmented energy minimization via speed scaling. In: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/af94ed0d6f5acc95f97170e3685f16c0-Abstract.html
[5] Bamas, É., Maggiori, A., Svensson, O.: The primal-dual method for learning augmented algorithms. In: Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual (2020). https://proceedings.neurips.cc/paper/2020/hash/e834cb114d33f729dbc9c7fb0c6bb607-Abstract.html
[6] Bhaskara, A., Cutkosky, A., Kumar, R., Purohit, M.: Online learning with imperfect hints. In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, vol. 119, pp. 822-831. PMLR (2020). http://proceedings.mlr.press/v119/bhaskara20a.html
[7] Dey, R., Salem, F.M.: Gate-variants of gated recurrent unit (GRU) neural networks. In: IEEE 60th International Midwest Symposium on Circuits and Systems, MWSCAS 2017, Boston, MA, USA, August 6-9, 2017, pp. 1597-1600 (2017). doi:10.1109/MWSCAS.2017.8053243
[8] Diao, R.; Liu, Y.; Dai, Y., A new fully polynomial time approximation scheme for the interval subset sum problem, J. Glob. Optim., 68, 4, 749-775 (2017) · Zbl 1380.90288 · doi:10.1007/s10898-017-0514-0
[9] Garey, MR; Johnson, DS, Computers and intractability: A guide to the theory of NP-completeness (1979), W. H: Freeman, W. H · Zbl 0411.68039
[10] Gollapudi, S., Panigrahi, D.: Online algorithms for rent-or-buy with expert advice. In: Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, Proceedings of Machine Learning Research, vol. 97, pp. 2319-2327. PMLR (2019). http://proceedings.mlr.press/v97/gollapudi19a.html
[11] Gupta, R.; Roughgarden, T., A PAC approach to application-specific algorithm selection, SIAM J. Comput., 46, 3, 992-1017 (2017) · Zbl 1371.68316 · doi:10.1137/15M1050276
[12] Han, X.; Kawase, Y.; Makino, K., Randomized algorithms for online knapsack problems, Theor. Comput. Sci., 562, 395-405 (2015) · Zbl 1303.68160 · doi:10.1016/j.tcs.2014.10.017
[13] Ibarra, OH; Kim, CE, Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM, 22, 4, 463-468 (1975) · Zbl 0345.90049 · doi:10.1145/321906.321909
[14] Jiang, Z., Panigrahi, D., Sun, K.: Online algorithms for weighted paging with predictions. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), LIPIcs, vol. 168, pp. 69:1-69:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). doi:10.4230/LIPIcs.ICALP.2020.69 · Zbl 07758433
[15] Kellerer, H.; Mansini, R.; Pferschy, U.; Speranza, MG, An efficient fully polynomial approximation scheme for the subset-sum problem, J. Comput. Syst. Sci., 66, 2, 349-370 (2003) · Zbl 1045.68157 · doi:10.1016/S0022-0000(03)00006-0
[16] Kellerer, H.; Pferschy, U., A new fully polynomial time approximation scheme for the knapsack problem, J. Comb. Optim., 3, 1, 59-71 (1999) · Zbl 0957.90112 · doi:10.1023/A:1009813105532
[17] Kothari, A., Suri, S., Zhou, Y.: Interval subset sum and uniform-price auction clearing. In: L. Wang (ed.) Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3595, pp. 608-620. Springer (2005). doi:10.1007/11533719_62 · Zbl 1128.91321
[18] Lattanzi, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Online scheduling via learned weights. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pp. 1859-1877. SIAM (2020). doi:10.1137/1.9781611975994.114 · Zbl 07304137
[19] Lavastida, T., Moseley, B., Ravi, R., Xu, C.: Learnable and instance-robust predictions for online matching, flows and load balancing. In: P. Mutzel, R. Pagh, G. Herman (eds.) 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), LIPIcs, vol. 204, pp. 59:1-59:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). doi:10.4230/LIPIcs.ESA.2021.59 · Zbl 07740914
[20] Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. In: Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, Proceedings of Machine Learning Research, vol. 80, pp. 3302-3311. PMLR (2018). http://proceedings.mlr.press/v80/lykouris18a.html · Zbl 1499.68415
[21] Ma, W., Simchi-Levi, D., Zhao, J.: A competitive analysis of online knapsack problems with unit density. SSRN Electronic Journal (2019)
[22] Magazine, MJ; Oguz, O., A fully polynomial approximation algorithm for the 0-1 knapsack problem, Eur. J. Oper. Res., 8, 3, 270-273 (1981) · Zbl 0473.90056 · doi:10.1016/0377-2217(81)90175-2
[23] Pisinger, D., Linear time algorithms for knapsack problems with bounded weights, J. Algorithm, 33, 1, 1-14 (1999) · Zbl 0951.90047 · doi:10.1006/jagm.1999.1034
[24] Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9684-9693 (2018). http://papers.nips.cc/paper/8174-improving-online-algorithms-via-ml-predictions
[25] Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pp. 1834-1845. SIAM (2020). doi:10.1137/1.9781611975994.112 · Zbl 07304135
[26] Wei, A.: Better and simpler learning-augmented online caching. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020, August 17-19, 2020, Virtual Conference, LIPIcs, vol. 176, pp. 60:1-60:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). doi:10.4230/LIPIcs.APPROX/RANDOM.2020.60 · Zbl 07758362
[27] Yao, A.C.: Probabilistic computations: Toward a unified measure of complexity (extended abstract). In: 18th Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1 November 1977, pp. 222-227. IEEE Computer Society (1977). doi:10.1109/SFCS.1977.24
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.