Learning-augmented algorithms for online subset sum

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.