In their seminal paper Moseley, Niaparast, and Ravi introduced the Joint Replenishment Problem (JRP) with holding and backlog costs that models the trade-off between ordering costs, holding costs, and backlog costs in supply chain planning systems. Their model generalized the classical make-to-order version as well maketo-stock version. For the case where holding costs function of all items are the same and all backlog costs are the same, they provide a constant competitive algorithm, leaving designing a constant competitive algorithm for arbitrary functions open. Moreover, they noticed that their algorithm does not work for arbitrary (request dependent) holding costs and backlog costs functions. We resolve their open problem and design a constant competitive algorithm that works for arbitrary request dependent functions. Specifically, we establish a 4-competitive algorithm for the single-item case and a 16-competitive for the general (multi-item) version. The algorithm of Moseley, Niaparast, and Ravi is based on fixed priority on the requests to items, and request to an item are always served by order of deadlines. In contrast, we design an algorithm with dynamic priority over the requests such that instead of servicing a prefix by deadline of requests, we may need to service a general subset of the requests.

List Update is a fundamental problem in online algorithms, with a well-known 2-competitive algorithm that moves every requested element to the front. Randomization can slightly improve the competitive ratio to 1.6, but not beyond 1.5. However, practical inputs are not adversarial and one hopes to do better, particularly when additional information from a machine learning oracle is available. With access to predictions, the goal is to incur only a slight overhead compared to the prediction's accuracy, avoiding significant costs in case of substantial deviation. We propose a (1+epsilon)-smooth randomized algorithm, offering robustness of O(1/epsilon^4). This guarantees that the algorithm never exceeds a cost greater than 1+epsilon times the prediction cost, while maintaining a bound within O(1/epsilon^4) of the optimal cost for every possible sequence. In cases where no paid swaps are permitted for the prediction, we can improve robustness to O(1/epsilon^2) while retaining 1+epsilon smoothness. We complement these findings by demonstrating a lower bound of 1/epsilon on the robustness for deterministic algorithms and log(1/epsilon) for randomized ones. Finally, the experiments we have made show that our algorithms perform better than the standard competitive algorithms for this problem

We consider the problem of List Update, one of the most fundamental problems in online algorithms. We are given a list of elements and requests for these elements that arrive over time. Our goal is to serve these requests, at a cost equivalent to their position in the list, with the option of moving them towards the head of the list. Sleator and Tarjan introduced the famous "Move to Front" algorithm (wherein any requested element is immediately moved to the head of the list) and showed that it is 2-competitive. While this bound is excellent, the absolute cost of the algorithm's solution may be very large (e.g., requesting the last half elements of the list would result in a solution cost that is quadratic in the length of the list). Thus, we consider the more general problem wherein every request arrives with a deadline and must be served, not immediately, but rather before the deadline. We further allow the algorithm to serve multiple requests simultaneously. We denote this problem as List Update with Time Windows. While this generalization benefits from lower solution costs, it requires new types of algorithms. In particular, for the simple example of requesting the last half elements of the list with overlapping time windows, Move-to-Front fails. We show an O(1) competitive algorithm. The algorithm is natural but the analysis is a bit complicated and a novel potential function is required. Thereafter we consider the more general problem of List Update with Delays in which the deadlines are replaced with arbitrary delay functions. This problem includes as a special case the prize collecting version in which a request might not be served (up to some deadline) and instead suffers an arbitrary given penalty. Here we also establish an O(1) competitive algorithm for general delays. The algorithm for the delay version is more complex and its analysis is significantly more involved.