Universal Optimization for Non-Clairvoyant Subadditive Joint Replenishment

Abstract

The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior works on JRP and its generalizations have focused on the clairvoyant setting. Recently, Touitou developed a non-clairvoyant framework that provided an $O(\sqrt{n \log n})$ upper bound for a wide class of generalized JRP, where $n$ is the number of request types.

We advance the study of non-clairvoyant algorithms by providing a simpler, modular framework that matches the competitive ratio established by Touitou for the same class of generalized JRP. Our key insight is to leverage universal algorithms for Set Cover to approximate arbitrary monotone subadditive functions using a simple class of functions termed disjoint. This allows us to reduce the problem to several independent instances of the TCP Acknowledgement problem, for which a simple 2-competitive non-clairvoyant algorithm is known. The modularity of our framework is a major advantage as it allows us to tailor the reduction to specific problems and obtain better competitive ratios. In particular, we obtain tight $O(\sqrt{n})$-competitive algorithms for two significant problems: Multi-Level Aggregation and Weighted Symmetric Subadditive Joint Replenishment. We also show that, in contrast, Touitou's algorithm is $\Omega(\sqrt{n \log n})$-competitive for both of these problems.

Michał Pawłowski

PhD Student

I am a Computer Science student interested in Online Algorithms and Probability Theory.