The field of learning-augmented algorithms seeks to use ML techniques on past instances of a problem to inform an algorithm designed for a future instance. In this paper, we introduce a novel model for learning-augmented algorithms inspired by online learning. In this model, we are given a sequence of instances of a problem and the goal of the learning-augmented algorithm is to use prior instances to propose a solution to a future instance of the problem. The performance of the algorithm is measured by its average performance across all the instances, where the performance on a single instance is the ratio between the cost of the algorithm's solution and that of an optimal solution for that instance. We apply this framework to the classic $k$-median clustering problem, and give an efficient learning algorithm that can approximately match the average performance of the best fixed $k$-median solution in hindsight across all the instances. We also experimentally evaluate our algorithm and show that its empirical performance is close to optimal, and also that it automatically adapts the solution to a dynamically changing sequence.

Best-Fit is one of the most prominent and practically used algorithms for the bin packing problem, where a set of items with associated sizes needs to be packed in the minimum number of unit-capacity bins. Kenyon [SODA ‘96] studied online bin packing under random-order arrival, where the adversary chooses the list of items, but the items arrive one by one according to an arrival order drawn uniformly at random from the set of all permutations of the items. Kenyon's seminal result established an upper bound of 1.5 and a lower bound of 1.08 on the random-order ratio of Best-Fit, and it was conjectured that the true ratio is ≍ 1.15. The conjecture, if true, will also imply that Best-Fit (on randomly permuted input) has the best performance guarantee among all the widely-used simple algorithms for (offline) bin packing. This conjecture has remained one of the major open problems in the area, as highlighted in the recent survey on random-order models by Gupta and Singla [Beyond the Worst-Case Analysis of Algorithms ‘20]. Recently, Albers et al. [Algorithmica ‘21] improved the upper bound to 1.25 for the special case when all the item sizes are greater than 1/3, and they improve the lower bound to 1.1. Ayyadevara et al. [ICALP ‘22] obtained an improved result for the special case when all the item sizes lie in (1/4,1/2], which corresponds to the 3-partition problem. The upper bound of 3/2 for the general case, however, has remained unimproved. This also has remained the best random-order ratio among all polynomial-time algorithms for online bin packing.