Improved Approximation Guarantees for
Joint Replenishment in Continuous Time

For a gradual presentation, let us begin by introducing the Economic Order Quantity (EOQ) model, which will imminently form the basic building block of joint replenishment settings. Here, we would like to identify the optimal time interval $T$ between successive orders of a single commodity, aiming to minimize its long-run average cost over the continuous planning horizon $[0,\infty)$. Specifically, this commodity is assumed to be characterized by a stationary demand rate of $d$, to be completely met upon occurrence; in other words, we do not allow for lost sales or back orders. In this setting, periodic policies are simply those where our ordering frequency is uniform across the planning horizon. Namely, orders will be placed at time points $0,T,2T,3T,\ldots$, noting that the time interval $T$ is the sole decision variable to be optimized. To understand the fundamental tradeoff, on the one hand, each of these orders incurs a fixed cost of $K$ regardless of its quantity, meaning that we are motivated to place very infrequent orders. On the other hand, what pulls in the opposite direction is a linear holding cost of $h$, incurred per time unit for each inventory unit in stock, implying that we wish to avoid high inventory levels via frequent orders. As such, the fundamental question is how to determine the time interval $T$, with the objective of minimizing long-run average ordering and holding costs.

Based on the preceding paragraph, it is not difficult to verify that optimal policies will be placing orders only when their on-hand inventory level is completely exhausted, namely, zero inventory ordering (ZIO) policies are optimal. Therefore, we can succinctly represent the objective function of interest,

with the convention that $H=\frac{hd}{2}$. The next claim gives a synopsis of several well-known properties exhibited by this function. We mention in passing that items 1-3 follow from elementary calculus arguments and can be found in most relevant textbooks; see, e.g., (Simchi-Levi et al., 1997, Sec. 7.1) (Zipkin, 2000, Sec. 3) (Muckstadt and Sapra, 2010, Sec. 2). In contrast, item 4 hides in various forms within previous literature, and we provide its complete proof in Appendix A.1.

With these foundations in place, the essence of joint replenishment can be captured by posing the next question: How should we coordinate multiple Economic Order Quantity models, when different commodities are tied together via joint ordering costs? Specifically, we wish to synchronize the lot sizing of $n$ distinct commodities, where each commodity $i\in[n]$ is coupled with its own EOQ model, parameterized by ordering and holding costs $K_{i}$ and $H_{i}$, respectively. As explained above, setting a time interval of $T_{i}$ between successive orders of this commodity would lead to a marginal operating cost of $C_{i}(T_{i})=\frac{K_{i}}{T_{i}}+H_{i}T_{i}$. However, the caveat is that we are concurrently facing joint ordering costs, paying $K_{0}$ whenever an order is placed, regardless of its particular subset of commodities.

Given these ingredients, it is convenient to represent any joint replenishment policy through a vector $T=(T_{1},\ldots,T_{n})$, where $T_{i}$ stands for the time interval between successive orders of each commodity $i\in[n]$. For such policies, the first component of our objective function encapsulates the sum of marginal EOQ-based costs, $\sum_{i\in[n]}C_{i}(T_{i})$. The second component, which will be designated by $J(T)$, captures long-run average joint ordering costs. Formally, this term is defined as the asymptotic density

where $N(T,\Delta)$ stands for the number of joint orders occurring across $[0,\Delta]$ with respect to the time intervals $T_{1},\ldots,T_{n}$. That is, letting ${\cal M}_{T_{i},\Delta}=\{0,T_{i},2T_{i},\ldots,\lfloor\frac{\Delta}{T_{i}}\rfloor\cdot T_{i}\}$ be the integer multiples of $T_{i}$ within $[0,\Delta]$, we have $N(T,\Delta)=|\bigcup_{i\in[n]}{\cal M}_{T_{i},\Delta}|$. In summary, our goal is to determine a joint replenishment policy $T=(T_{1},\ldots,T_{n})$ that minimizes long-run average operating costs, represented by

When one comes across representation (1) of the joint ordering term, it is only natural to ask why $\lim_{\Delta\to\infty}\frac{N(T,\Delta)}{\Delta}$ necessarily exists for any given policy $T$. To clarify this point, for any subset of commodities ${\cal N}\subseteq[n]$, let $M_{\cal N}$ be the least common multiple of $\{T_{i}\}_{i\in{\cal N}}$, with the agreement that $M_{\cal N}=\infty$ when these time intervals do not have common multiples. Lemma 1.2 below states a well-known observation, showing that the limit in question indeed exists and providing an explicit inclusion-exclusion-like formula; for a complete proof, we refer the reader to (Segev, 2023, Sec. 1.1). That said, since the resulting expression consists of $2^{n}$ terms, its current form does not allow us to efficiently compute the joint ordering cost of arbitrarily-structured policies, implying that our algorithmic developments would have to circumvent this obstacle.

To the best of our knowledge, the now-classical works of Roundy (1985, 1986), Jackson et al. (1985), Maxwell and Muckstadt (1985), and Muckstadt and Roundy (1987) were the first to devise efficient and provably-good policies for the joint replenishment problem. At a high level, these papers proposed innovative ways to exploit natural convex relaxations, rounding their optimal solutions to so-called power-of-$2$ policies. Within the latter class, one fixes a common base, say $T_{\min}$, with each time interval $T_{i}$ being of the form $2^{q_{i}}\cdot T_{\min}$, for some integer $q_{i}\geq 0$. Let us first examine the variable-base joint replenishment setting, where $T_{1},\ldots,T_{n}$ are allowed to take arbitrary values. Quite amazingly, this mechanism for synchronizing joint orders can be employed to optimize $T_{\min}$ and $\{q_{i}\}_{i\in[n]}$, ending up with a power-of-$2$ policy whose long-run average cost is within factor $\frac{1}{\sqrt{2}\ln 2}\approx 1.02$ of optimal! Since then, these findings have become some of the most renowned breakthroughs in inventory management, due to their widespread applicability, both theoretically and in practice.

With the above-mentioned approximation guarantee standing for nearly four decades, our recent work (Segev, 2023) finally attained the long-awaited improvement, showing that optimal policies can be efficiently approximated within any degree of accuracy. Technically speaking, this paper developed a new algorithmic approach for addressing the variable-base model, termed $\Psi$-pairwise alignment, enabling us to determine a replenishment policy whose long-run average cost is within factor $1+\epsilon$ of optimal. For any $\epsilon\in(0,\frac{1}{2})$, the running time of our algorithm is $O(2^{\tilde{O}(1/\epsilon^{3})}\cdot n^{O(1)})$, corresponding to the notion of an efficient polynomial-time approximation scheme (EPTAS).

Unfortunately, both the design of such policies and their analysis are very involved, mostly due to utilizing an exponentially-large value for the alignment parameter, $\Psi=2^{\mathrm{poly}(1/\epsilon)}$. The latter choice, which seems unavoidable in light of our cost-bounding arguments, concurrently leads to an $\tilde{O}(\frac{1}{\epsilon^{3}})$ running time exponent. Consequently, the primary open questions that motivate Section 2 of the present paper can be briefly summarized as follows:

• •

  Can we come up with simpler arguments for analyzing $\Psi$-pairwise alignment?

• •

  Is this method sufficiently accurate with $\Psi=\mathrm{poly}(1/\epsilon)$?

• •

  If doable, what are the running time implications of such improvements?

Now, let us shift our attention to the fixed-base joint replenishment setting, where the time intervals $T_{1},\ldots,T_{n}$ are restricted to being integer multiples of a prespecified time unit, $\Delta$. As one discovers by delving into previously-mentioned surveys (Aksoy and Erenguc, 1988; Goyal and Satir, 1989; Muckstadt and Roundy, 1993; Khouja and Goyal, 2008; Bastos et al., 2017), the latter requirement is motivated by real-life applications, where for practical concerns, cycle times are expected to be days, weeks, or months; here, policies with $T_{i}=\sqrt{e}$ or $T_{i}=\ln 7$, for example, cannot be reasonably implemented.

Yet another great achievement of Roundy (1985, 1986), Jackson et al. (1985), and subsequent authors resides in proposing an ingenious rounding method for efficiently identifying feasible power-of-$2$ policies whose long-run average cost is within factor $\sqrt{9/8}\approx 1.06$ of optimal! Here, to ensure feasibility, rather than allowing the common base $T_{\min}$ to take arbitrary values, one should optimize this parameter over integer multiples of the basic unit, $\Delta$, explaining why approaching optimal policies in this model appears to be more challenging in comparison to its variable-base counterpart. While $\sqrt{9/8}\approx 1.06$ is widely believed to be the best approximation guarantee in this context, it has actually been surpassed years ago by Teo and Bertsimas (2001, Sec. 4). Their work developed a very elegant randomized rounding method for approximating the fixed-base joint replenishment problem within a factor of roughly $1.043$.

Unfortunately, due to a host of technical difficulties, we still do not know whether the notion of $\Psi$-pairwise alignment, in any conceivable form, can be adapted to provide improved approximation guarantees for the fixed-base setting. Given this state of affairs, the fundamental questions driving Section 3 of the present work, as stated in countless papers, books, conference talks, and course materials, can be concisely recapped as follows:

• •

  Can we outperform the above-mentioned results, in any shape or form?

• •

  It is easy to see why approximation guarantees for the fixed-base model readily migrate to the variable-base case; what about the opposite direction?

Somewhat informally, the term “integer-ratio” has been coined by classical literature to capture families of replenishment policies $(T_{1},\ldots,T_{n})$ for which there exists some $T_{0}>0$, such that the ratio $\frac{T_{i}}{T_{0}}$ is either an integer or its reciprocal, for every commodity $i\in[n]$. To qualify the slight informality, we mention that one could ask $\frac{T_{1}}{T_{0}},\ldots,\frac{T_{n}}{T_{0}}$ to reside within some proper subset $R$ of the positive integers and their reciprocals, in which case we arrive at $R$-integer-ratio policies or at additional twists on this terminology.

Needless to say, power-of-$2$ policies are high-structured special cases of integer-ratio policies, since we are fixing a common base $T_{\min}$ and restricting each time interval $T_{i}$ to take the form $2^{q_{i}}\cdot T_{\min}$, for some integer $q_{i}\geq 0$. From this perspective, one could view existing $\frac{1}{\sqrt{2}\ln 2}$-approximations for the variable-base joint replenishment problem as utilizing a very specific type of integer-ratio policies. Interestingly, to this day, $\frac{1}{\sqrt{2}\ln 2}$ constitutes the best-known factor achievable through integer-ratio policies, and it is entirely unclear whether the latter family offers strictly stronger performance guarantees. To motivate Section 4 of this paper, we take the following quote from the concluding remarks of Roundy’s seminal work (1985, Sec. 8), stating a well-known conjecture about how good could integer-ratio policies potentially be:

“It is likely that by using a somewhat more general class of policies, such as allowing $r_{n}=2/3$ or $r_{n}=3/2$, or by finding an optimal integer-ratio policy, the worst-case effectiveness of the lot-sizing rules given herein could be improved”.

A common thread passing across all settings reviewed up until now is that different commodities are interacting “only” via their joint orders. Last but not least, we will be considering the resource-constrained joint replenishment problem, where the underlying commodities are further connected through the following family of constraints:

While serving a wide range of practical purposes, it is instructive to take a production-oriented view on this model, where assembling each commodity $i$ requires $D$ limited resources. In turn, deciding on a time interval of $T_{i}$ between successive orders translates to consuming $\frac{\alpha_{id}}{T_{i}}$ units of each resource $d\in[D]$, whose overall capacity is denoted by $\beta_{d}$. For an elaborate discussion on the theoretical and practical usefulness of such constraints and their rich history, one could consult the classical work of Dobson (1987), Jackson et al. (1988), and Roundy (1989) along these lines.

Unfortunately, resource constraints appear to be rendering the joint replenishment problem significantly more difficult to handle in comparison to its unrestricted counterpart. To our knowledge, Roundy (1989) still holds the best approximation guarantee in this context, showing that sophisticated scaling arguments lead to the design of power-of-$2$ policies whose long-run average cost is within factor $\frac{1}{\ln 2}\approx 1.442$ of optimal. Interestingly, subject to a single resource constraint, Roundy (1989) proved that the latter approximation guarantee can be improved to $\sqrt{9/8}\approx 1.06$, and we refer readers to the work of Teo and Bertsimas (2001) for very elegant methods to derive these results via randomized rounding. Given that the above-mentioned findings have been state-of-the-art for about 3.5 decades, the open questions that will lie at the heart of Sections 5 and 6 can be succinctly highlighted as follows:

• •

  For the general problem setup, can we devise improved rounding methods, perhaps deviating from power-of-$2$ policies?

• •

  For a single resource constraint, could $\Psi$-pairwise alignment be exploited to breach the $\sqrt{9/8}$-barrier?

Even though our work is algorithmically driven, to better understand the overall landscape, it is worth briefly mentioning known intractability results. Along these lines, Schulz and Telha (2011) were the first to rigorously investigate how plausible it is to efficiently compute optimal replenishment policies in continuous time. Specifically, they proved that in the fixed-base setting, a polynomial time algorithm for the joint replenishment problem would imply an analogous result for integer factorization, thereby unraveling well-hidden connections between this question and fundamental problems in number theory. Subsequently, following Zhang’s extraordinary work (2014) on bounded gaps between successive primes, Cohen-Hillel and Yedidsion (2018) attained traditional complexity-based results, proving that the fixed-base setting is in fact strongly NP-hard. The latter result has been substantially simplified by Schulz and Telha (2024), showing that NP-hardness arises even in the presence of only two commodities. Finally, for the variable-base setting, Schulz and Telha (2024) extended their original findings to derive its polynomial-relatability to integer factorization. The latter result was further lifted to a strong NP-hardness proof by Tuisov and Yedidsion (2020).

In Section 2, we propose a new approach to streamline $\Psi$-pairwise alignment, simplifying the design principles of this framework and sharpening its performance guarantees. Interestingly, rather than utilizing an exponentially-large alignment parameter, our analysis will reveal that $\Psi=\tilde{O}(\frac{1}{\epsilon^{3}})$ suffices to identify $(1-\epsilon)$-approximate replenishment policies, while concurrently improving the running time exponent from $\tilde{O}(\frac{1}{\epsilon^{3}})$ to $\tilde{O}(\frac{1}{\epsilon})$. The outcome of this analysis can be formalized as follows.

In Section 3, we describe a black-box reduction, showing that any approximation guarantee with respect to the variable-base convex relaxation (Roundy, 1985, 1986; Jackson et al., 1985) readily migrates to the fixed-base joint replenishment problem, while incurring negligible loss in optimality. As an immediate implication, it follows that the fixed-base model can be efficiently approximated within factor $\frac{1}{\sqrt{2}\ln 2}+\epsilon$. The specifics of this result, which surpasses the long-standing performance guarantees of $1.043$ due to Teo and Bertsimas (2001), can be briefly stated as follows.

In Section 4, we resolve Roundy’s conjecture in the affirmative, improving on the best-known approximation factor achievable through integer-ratio policies, $\frac{1}{\sqrt{2}\ln 2}\approx 1.02014$. Quite surprisingly, evenly-spaced policies will be shown to offer strictly stronger performance guarantees in comparison to their power-of-$2$ counterparts. In the former class of policies, we decide in advance to place evenly-spaced joint orders, and subsequently set all time intervals $T_{1},\ldots,T_{n}$ as integer multiples of our spacing parameter, $\Delta$, which is a decision variable.

It is important to emphasize that, for ease of presentation, we have not fully optimized the above-mentioned constant, which should primarily be viewed as a proof of concept. Possible avenues toward improvements in this context are discussed in Section 7. From a computational perspective, we will explain how to efficiently compute an evenly-spaced policy whose long-run average cost is within factor $1+\epsilon$ of the optimal such policy. From a practical standpoint, we expect evenly-spaced policies to be particularly appealing, mainly due to their simplicity and implementability.

In Section 5, we revisit a well-known convex relaxation of the resource-constrained joint replenishment problem, thinking about how optimal solutions can be better converted into feasible policies. By fusing together classical ideas and new structural insights, we devise a randomized rounding procedure that breaches the best-known approximation factor in this setting, $\frac{1}{\ln 2}\approx 1.442$ (Roundy, 1989). Once again, for simplicity of presentation, we avoid making concentrated efforts to minimize the resulting constant.

Finally, in Section 6, we study the extent to which performance guarantees can be stretched, when running times are allowed to be exponential in the number of resource constraints, $D$. Along these lines, we propose an $O(n^{\tilde{O}(D^{3}/\epsilon^{4})})$-time enumeration-based approach for developing a linear relaxation, arguing that its optimal fractional solution can be rounded into a near-optimal resource-feasible policy. The specifics of this result can be succinctly summarized as follows.

One consequence of the latter finding is that, when $D=O(1)$, we actually obtain a polynomial-time approximation scheme (PTAS). In particular, by setting $D=1$, this outcome improves on the classic $\sqrt{9/8}$-approximation for a single resource constraint (Roundy, 1989; Teo and Bertsimas, 2001).

Let us make use of $T^{*}=(T_{1}^{*},\ldots,T_{n}^{*})$ to denote an optimal replenishment policy, fixed from this point on, with $T_{\min}^{*}=\min_{i\in[n]}T_{i}^{*}$ being the minimal time interval of any commodity. Given an error parameter $\epsilon\in(0,\frac{1}{2})$, we classify each interval $T_{i}^{*}$ as being large when $T_{i}^{*}>\frac{1}{\epsilon}\cdot T^{*}_{\min}$. In the opposite scenario, $T_{i}^{*}\in[T^{*}_{\min},\frac{1}{\epsilon}\cdot T^{*}_{\min}]$, in which case this interval will be referred to as being small. For a refined treatment of the latter class, we geometrically partition $[T^{*}_{\min},\frac{1}{\epsilon}\cdot T^{*}_{\min}]$ by powers of $1+\epsilon$, to obtain the sequence of segments $S_{1}^{*},\ldots,S_{L}^{*}$. Specifically,

so on and so forth, where in general $S_{\ell}^{*}=[(1+\epsilon)^{\ell-1}\cdot T^{*}_{\min},(1+\epsilon)^{\ell}\cdot T^{*}_{\min})$. Here, $L$ is the minimal integer $\ell$ for which $(1+\epsilon)^{\ell}\geq\frac{1}{\epsilon}$, meaning that $L=\lceil\log_{1+\epsilon}(\frac{1}{\epsilon})\rceil\leq\frac{2}{\epsilon}\ln\frac{1}{\epsilon}$.

We say that the segment $S_{\ell}^{*}$ is active when there is at least one commodity $i\in[n]$ with $T_{i}^{*}\in S_{\ell}^{*}$, letting ${\cal A}^{*}\subseteq[L]$ be the index set of active segments. Next, for each active segment $S_{\ell}^{*}$, let $R^{*}_{\ell}$ be an arbitrarily picked interval $T_{i}^{*}$ that belong to this segment; $R^{*}_{\ell}$ will be called the representative of $S_{\ell}^{*}$.

We proceed by listing two useful observations regarding the set of representatives ${\cal R}^{*}=\{R^{*}_{\ell}\}_{\ell\in{\cal A}^{*}}$. First, Observation 2.1 informs us that, for every $\Delta\geq 0$, the number of joint orders across $[0,\Delta]$ with respect to the time intervals ${\cal R}^{*}$ is upper-bounded by the analogous quantity with respect to the optimal policy $T^{*}$; this claim can be straightforwardly inferred by noting that ${\cal R}^{*}\subseteq\{T_{1}^{*},\ldots,T_{n}^{*}\}$. Second, Observation 2.2 indirectly states that $S_{1}^{*}$ must be an active segment, meaning that its representative $R_{1}^{*}$ belongs to ${\cal R}^{*}$. To verify this claim, it suffices to note that $T_{\min}^{*}\in S_{1}^{*}$, by definition (2) of this segment.

We say that a pair of active segments $S_{\ell_{1}}^{*}$ and $S_{\ell_{2}}^{*}$ is aligned when their representatives $R^{*}_{\ell_{1}}$ and $R^{*}_{\ell_{2}}$ have common integer multiples, which is equivalent to $\frac{R^{*}_{\ell_{1}}}{R^{*}_{\ell_{2}}}$ being a rational number. Moving on to define a stronger requirement, letting $M_{\ell_{1},\ell_{2}}^{*}$ be the least common multiple of $R^{*}_{\ell_{1}}$ and $R^{*}_{\ell_{2}}$, this pair of segments is called $\Psi$-aligned when the corresponding multiples $\frac{M_{\ell_{1},\ell_{2}}^{*}}{R^{*}_{\ell_{1}}}$ and $\frac{M_{\ell_{1},\ell_{2}}^{*}}{R^{*}_{\ell_{2}}}$ both take values of at most $\Psi$, with the latter constant set to $\Psi=\frac{2}{\epsilon^{3}}\ln^{2}(\frac{1}{\epsilon})$. In this case, we make use of $\alpha^{*}_{\{\ell_{1},\ell_{2}\},\ell_{1}}$ and $\alpha^{*}_{\{\ell_{1},\ell_{2}\},\ell_{2}}$ to denote these two multiples, respectively. It is worth pointing out that, since $\Psi$ is chosen to be polynomial in $\frac{1}{\epsilon}$, we will have to come up with cost-bounding arguments that are significantly different from those of our recent work (Segev, 2023), which are relevant only when $\Psi=2^{\mathrm{poly}(1/\epsilon)}$.

Letting ${\cal P}_{\Psi}^{*}$ be the collection of $\Psi$-aligned pairs, in subsequent sections we will be exploiting the so-called alignment graph, $G_{\Psi}^{*}=({\cal A}^{*},{\cal P}_{\Psi}^{*})$. Namely, the vertex set of this graph is comprised of the active segments, and each pair of such segments is connected by an edge when they are $\Psi$-aligned. We make use of ${\cal C}_{1}^{*},\ldots,{\cal C}_{\Lambda}^{*}$ to denote the underlying connected components of $G_{\Psi}^{*}$.

For any pair of connected components ${\cal C}_{\lambda_{1}}^{*}\neq{\cal C}_{\lambda_{2}}^{*}$, we obtain the upper bound in question by observing that

To better understand where inequality (6) is coming from, the important observation is that, for any pair of segments $\ell_{1}$ and $\ell_{2}$ in different connected components of $G_{\Psi}^{*}$, we know that $R^{*}_{\ell_{1}}$ and $R^{*}_{\ell_{2}}$ are not $\Psi$-aligned. Namely, $R^{*}_{\ell_{1}}$ and $R^{*}_{\ell_{2}}$ either do not have common integer multiples, or have their least common multiple being greater than $\Psi\cdot\min\{R^{*}_{\ell_{1}},R^{*}_{\ell_{2}}\}$. Inequality (7) holds since both $R^{*}_{\ell_{1}}$ and $R^{*}_{\ell_{2}}$ take values of at least $T^{*}_{\min}$. Finally, inequality (8) is obtained by noting that $N({\cal R}^{*},\Delta)\geq\frac{\Delta}{T_{\min}^{*}}$.

Starting with the easy scenario, we argue that when the optimal joint ordering cost $J(T^{*})$ is sufficiently small in comparison to $\widetilde{\mathrm{OPT}}$, a rather straightforward replenishment policy is near-optimal. To this end, our candidate policy $\tilde{T}=(\tilde{T}_{1},\ldots,\tilde{T}_{n})$ is determined as follows:

• •

  Placing joint orders: We place joint order at integer multiples of $\Delta=\frac{K_{0}}{\epsilon\widetilde{\mathrm{OPT}}}$.

• •

  Placing commodity-specific orders: For each commodity $i\in[n]$, let $T_{i}^{\mathrm{EOQ}}$ be the optimal solution to the standard EOQ model of this commodity (see Section 1.1). Namely, $T_{i}^{\mathrm{EOQ}}$ minimizes the long-run average cost $C_{i}(T_{i})=\frac{K_{i}}{T_{i}}+H_{i}T_{i}$, implying that $T_{i}^{\mathrm{EOQ}}=\sqrt{K_{i}/H_{i}}$ by Claim 1.1. Given these definitions, we set the time interval of commodity $i$ as $\tilde{T}_{i}=\lceil T_{i}^{\mathrm{EOQ}}\rceil^{(\Delta)}$, where $\lceil\cdot\rceil^{(\Delta)}$ is an operator that rounds its argument up to the nearest integer multiple of $\Delta$.

The next claim shows that, in the currently considered regime, this policy happens to be near-optimal.

We have now landed at the difficult scenario, where the vast majority of algorithmic effort is required. In Sections 2.4-2.6, our objective is to efficiently construct a set of representative points $\tilde{\cal R}\subseteq\mathbbm{R}_{+}$ that “mimics” the unknown set of optimal representatives ${\cal R}^{*}=\{R^{*}_{\ell}\}_{\ell\in{\cal A}^{*}}$, in the sense of simultaneously being $\epsilon$-dense and $\epsilon$-assignable. To better understand these properties, it is instructive to keep in mind the following interpretation:

1. 1.

   One-to-one correspondence: This notion means that our set of representatives can be written as $\tilde{\cal R}=\{\tilde{R}_{\ell}\}_{\ell\in{\cal A}^{*}}$. We mention in passing that, while each optimal representative $R^{*}_{\ell}$ resides within $S^{*}_{\ell}$, its analogous $\tilde{R}_{\ell}$ will be allowed to slightly exceed this segment.

2. 2.

   $\epsilon$-density: The set $\tilde{\cal R}$ is called $\epsilon$-dense when, by placing joints orders at all integer multiples of all representative points, we obtain an ordering density $\lim_{\Delta\to\infty}\frac{N(\tilde{\cal R},\Delta)}{\Delta}$ that matches the analogous density $\lim_{\Delta\to\infty}\frac{N(T^{*},\Delta)}{\Delta}$ with respect to the optimal policy $T^{*}$, up to a factor of $1+\epsilon$. By representation (1), this property translates to $J(\tilde{\cal R})\leq(1+\epsilon)\cdot J(T^{*})$, implying that our long-run joint ordering cost is near-optimal.

3. 3.

   $\epsilon$-assignability: We say that $\tilde{\cal R}$ is $\epsilon$-assignable when, for each commodity $i\in[n]$, we can choose an integer multiple of some representative in $\tilde{\cal R}$ to serve as the time interval $\tilde{T}_{i}$ of this commodity, such that its marginal operating cost $C_{i}(\tilde{T}_{i})$ is within factor $1+\epsilon$ of the analogous cost $C_{i}(T_{i}^{*})$ with respect to $T^{*}$.

Let us first observe that, since $\frac{1}{T^{*}_{\min}}$ forms an upper bound on the ordering frequency of each commodity, we have $J(T^{*})\leq\frac{nK_{0}}{T_{\min}^{*}}$. Combining the latter inequality with our case hypothesis in the expensive ordering regime, $J(T^{*})>\epsilon^{2}\widetilde{\mathrm{OPT}}$, it follows that $T_{\min}^{*}\leq\frac{n}{\epsilon^{2}}\cdot\frac{K_{0}}{\widetilde{\mathrm{OPT}}}$. On the other hand, $\frac{K_{0}}{T_{\min}^{*}}\leq J(T^{*})<F(T^{*})\leq\widetilde{\mathrm{OPT}}$, meaning that $T_{\min}^{*}\geq\frac{K_{0}}{\widetilde{\mathrm{OPT}}}$. As such, we know that the minimal time interval $T_{\min}^{*}$ resides within $[\frac{K_{0}}{\widetilde{\mathrm{OPT}}},\frac{n}{\epsilon^{2}}\cdot\frac{K_{0}}{\widetilde{\mathrm{OPT}}})$. By enumerating over $O(\frac{1}{\epsilon}\log\frac{n}{\epsilon})$ candidate values, this property allows us to assume that we have at our possession an under-estimate $\tilde{T}_{\min}$ of the minimal time interval $T_{\min}^{*}$, specifically, one that satisfies

Recalling that ${\cal A}^{*}\subseteq[L]$ stands for the index set of active segments, this set is clearly unknown from an algorithmic perspective. Therefore, our next step consists of guessing the precise identity of ${\cal A}^{*}$, or equivalently, whether each of the segments $S_{1}^{*},\ldots,S_{L}^{*}$ is active or not. For this purpose, the overall number of guesses to consider is $2^{L}=O(2^{O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})})$.

As explained in Section 2.1, the alignment graph $G_{\Psi}^{*}=({\cal A}^{*},{\cal P}_{\Psi}^{*})$ is a useful way to view the collection of $\Psi$-aligned pairs and to study their relationships. In this graph, our vertex set is comprised of the active segments ${\cal A}^{*}$, which is already known following step 2. However, noting that $G_{\Psi}^{*}$ connects each pair of such segments by an edge when they are $\Psi$-aligned, we are still unaware of how this edge set ${\cal P}_{\Psi}^{*}$ is structured. Moving forward, we will not be guessing the precise identity of ${\cal P}_{\Psi}^{*}$, which would require us to consider all $2^{\Omega(|{\cal A}^{*}|^{2})}$ possible subsets of edges, and in turn, to exceed the $O(2^{\tilde{O}(1/\epsilon)}\cdot n^{O(1)})$ running time guarantee stated in Theorem 1.3.

Instead, let us remind the reader that the underlying connected components of $G_{\Psi}^{*}$ were designated by ${\cal C}_{1}^{*},\ldots,{\cal C}_{\Lambda}^{*}$. Letting ${\cal T}^{*}_{\lambda}$ be an arbitrary spanning tree of each such component ${\cal C}_{\lambda}^{*}$, we proceed by guessing the entire forest ${\cal F}^{*}=\{{\cal T}^{*}_{1},\ldots,{\cal T}^{*}_{\Lambda}\}$. To this end, it suffices to enumerate across all possible forests over the set of vertices ${\cal A}^{*}$, where by Cayley’s formula (see, e.g., Aigner and Ziegler (2018, pg. 235-240)), there are only $|{\cal A}^{*}|^{O(|{\cal A}^{*}|)}=O(2^{O(\frac{1}{\epsilon}\log^{2}(\frac{1}{\epsilon}))})$ forests to consider.

Noting that ${\cal F}^{*}$ is a spanning forest of the alignment graph $G_{\Psi}^{*}$, we know that for each edge $(\ell_{1},\ell_{2})\in{\cal F}^{*}$, its corresponding pair $(R^{*}_{\ell_{1}},R^{*}_{\ell_{2}})$ of optimal representatives is $\Psi$-aligned. In other words, letting $M_{\ell_{1},\ell_{2}}^{*}$ be the least common multiple of $R^{*}_{\ell_{1}}$ and $R^{*}_{\ell_{2}}$, the corresponding multiples $\alpha^{*}_{\{\ell_{1},\ell_{2}\},\ell_{1}}=\frac{M_{\ell_{1},\ell_{2}}^{*}}{R^{*}_{\ell_{1}}}$ and $\alpha^{*}_{\{\ell_{1},\ell_{2}\},\ell_{2}}=\frac{M_{\ell_{1},\ell_{2}}^{*}}{R^{*}_{\ell_{2}}}$ both take values of at most $\Psi=\frac{2}{\epsilon^{3}}\ln^{2}(\frac{1}{\epsilon})$. Consequently, we can guess the latter multiples for all edges in ${\cal F}^{*}$ by enumerating over $O(\Psi^{O(|E({\cal F}^{*})|)})=O(2^{O(\frac{1}{\epsilon}\log^{2}(\frac{1}{\epsilon}))})$ options.

Given these ingredients, our revised method for defining the set of approximate representatives $\tilde{\cal R}=\{\tilde{R}_{\ell}\}_{\ell\in{\cal A}^{*}}$ makes completely independent decisions for each of the trees ${\cal T}^{*}_{1},\ldots,{\cal T}^{*}_{\Lambda}$. Specifically, focusing on a single tree ${\cal T}^{*}_{\lambda}$, let $\sigma_{\lambda}$ be an arbitrarily picked vertex in ${\cal T}^{*}_{\lambda}$, to which we refer as the source of this tree. Recalling that $R^{*}_{\sigma_{\lambda}}$ is the representative of $S_{\sigma_{\lambda}}^{*}=[(1+\epsilon)^{\sigma_{\lambda}-1}\cdot T^{*}_{\min},(1+\epsilon)^{\sigma_{\lambda}}\cdot T^{*}_{\min})$, we begin by setting $\tilde{R}_{\sigma_{\lambda}}=(1+\epsilon)^{\sigma_{\lambda}}\cdot\tilde{T}_{\min}$, which corresponds to the right endpoint of this segment, with the unknown $T^{*}_{\min}$ replaced by its estimate, $\tilde{T}_{\min}$. As a side note, any choice of $\tilde{R}_{\sigma_{\lambda}}$ that can be $(1\pm O(\epsilon))$-scaled back into $S_{\sigma_{\lambda}}^{*}$ will be good enough for our purposes; choosing $\tilde{R}_{\sigma_{\lambda}}$ as a proxy for the right endpoint is mainly for notational convenience.

The important observation is that, once we fix a particular value for a single representative in ${\cal T}^{*}_{\lambda}$, all other representatives in this tree are uniquely determined through the multiples $\{(\alpha^{*}_{\{\ell_{1},\ell_{2}\},\ell_{1}},\alpha^{*}_{\{\ell_{1},\ell_{2}\},\ell_{2}}):(\ell_{1},\ell_{2})\in{\cal T}^{*}_{\lambda}\}$. Indeed, let us consider some vertex $\ell\in{\cal T}^{*}_{\lambda}$, with $\sigma_{\lambda}=u_{1},\ldots,u_{k}=\ell$ being the sequence of vertices along the unique $\sigma_{\lambda}$-$\ell$ path in ${\cal T}^{*}_{\lambda}$. We first observe that since $(u_{1},u_{2})\in{\cal T}^{*}_{\lambda}\subseteq G_{\Psi}^{*}$, to instill the exact same $\Psi$-alignment between $\tilde{R}_{u_{1}}$ and $\tilde{R}_{u_{2}}$, one should enforce $\alpha^{*}_{\{u_{1},u_{2}\},u_{1}}\cdot\tilde{R}_{u_{1}}=\alpha^{*}_{\{u_{1},u_{2}\},u_{2}}\cdot\tilde{R}_{u_{2}}$ for this particular pair. Similarly, since $(u_{2},u_{3})$ is an edge of $G_{\Psi}^{*}$, this constraint sets $\alpha^{*}_{\{u_{2},u_{3}\},u_{2}}\cdot\tilde{R}_{u_{2}}=\alpha^{*}_{\{u_{2},u_{3}\},u_{3}}\cdot\tilde{R}_{u_{3}}$. Letting this relation propagate throughout the entire $\sigma_{\lambda}$-$\ell$ path, its resulting sequence of equations can be aggregated to obtain a unique value for the representative $\tilde{R}_{\ell}$, given by:

An important consequence of the preceding discussion is that our explanation of how a single representative determines its entire component applies to the collection of optimal representatives $\{R_{\ell}^{*}\}_{\ell\in{\cal A}^{*}}$ as well. In particular, for every tree ${\cal T}^{*}_{\lambda}$ and for every vertex $\ell\in{\cal T}^{*}_{\lambda}$, we know that