MSOM-22-390.R1

Order-optimal Correlated Rounding for Fulfilling Multi-item E-commerce Orders

Will Ma Graduate School of Business, Columbia University, New York, NY 10027,
<EMAIL_ADDRESS>
We study a parsimonious correlated rounding problem motivated by e-commerce
fulfillment. In this problem, we are given a multi-item order of size $q$; for
each item $i=1,\ldots,q$, we are given the probability $u_{ki}$ with which it
must be shipped from each Fulfillment Center (FC) $k=1,\ldots,K$, with
$\sum_{k=1}^{K}u_{ki}=1$. The goal is to randomly select a FC to ship each
item following these marginal probabilities $u_{ki}$ (motivated by trying to
satisfy long-run inventory flow), in a way that not many distinct FC’s end up
being used (motivated by reducing the number of boxes that need to be
shipped). In particular, the objective is to use each FC with probability at
most $\alpha\cdot y_{k}$, where $y_{k}:=\max_{i=1,\ldots,q}u_{ki}$ is a lower
bound on the probability with which FC $k$ must be used, and $\alpha\geq 1$ is
the guarantee to be made as small as possible.

This problem was originally introduced in Jasin and Sinha (2015), who present
a rounding scheme that guarantees $\alpha\approx q/4$ given any $q$ marginal
distributions. Our main result is a rounding scheme that guarantees
$\alpha=\ln(q)+1$, significantly improving the order-dependence on $q$ from
linear to logarithmic. We present another rounding scheme for sparse networks,
that guarantees $\alpha=d$ if each item is stored in at most $d$ FC’s. We show
these guarantees to be tight in terms of the dependence on $q$ or $d$. Our
schemes are simple and fast, based on two intuitive ideas—items wait for FC’s
to “open” following Poisson clocks, and observe them on “dilated” time scales.
The first idea positively correlates the FC’s selected by items so that not
many FC’s are used; the second idea ensures that the marginal probability
constraints are satisfied.

Interestingly, our main result implies a simple new correlated rounding scheme
for the Set Cover randomized rounding problem. Given a fractional set cover,
it outputs an integral cover in which each set is selected with probability at
most $\ln(q)+1$ times its fractional weight. This improves the constant term
from existing rounding schemes for Set Cover, which select each set with
probability at least $\ln(q)+\omega(1)$ times its fractional weight.

Returning to the e-commerce application, it has been shown in Jasin and Sinha
(2015) that results for this correlated rounding problem have direct
implications for a dynamic fulfillment problem in which different multi-item
orders arrive over time and there are inventory constraints. We numerically
test our rounding schemes under the dynamic fulfillment setups from Jasin and
Sinha (2015) and find that they improve runtimes, shorten code, and robustly
improve performance. We make our code publicly available.

Full version of EC2023 paper

##  1 Introduction

E-commerce has exploded in recent times, achieving unbelievable global scale,
delivery speed, and system complexity. The short-term operations of a typical
e-commerce giant involves pulling inventory from suppliers into its
fulfillment centers (FC’s), including retail stores that can also be used to
fulfill online orders; awaiting purchases from online customers, which can be
influenced by a powerful search/recommendation engine; and finally delivering
the goods to the customer’s doorstep, through a flexible transportation system
that allows different FC’s in the network to be used for fulfilling demand
from any particular region.

This paper focuses on the final part of these operations, which is the problem
of dynamically dispatching incoming customer orders to FC’s, while treating
this customer demand (as influenced by search/recommendation) and inventory
replenishment as exogenous. The decision is on how to dynamically allocate
finite inventories, of multiple items each of which has been placed in
multiple FC’s, over a finite time horizon, representing the duration until the
next inventory replenishment. The objective is to minimize the total costs
from fulfillment and inventory stockouts.

This dynamic fulfillment problem is challenging for several reasons. First,
decisions must be made with consideration of the future orders to come, since
depleting inventories at the wrong places can set off a chain reaction of
long-distance and split shipments, as originally demonstrated by Xu et al.
(2009). Moreover, due to the uncertainty in future orders, forward-lookingness
requires a high-dimensional stochastic dynamic program that is intractable to
solve, as noted by Acimovic and Farias (2019). Finally, the mere scale and
speed of the problem restricts us to fast and simple heuristics, with more
elaborate optimizations exacerbating the issue of system complexity.

In light of these challenges, a prevailing approach to the dynamic fulfillment
problem is deterministic-relaxation-based, as pioneered by Jasin and Sinha
(2015). Namely, a linear program (LP) that views the system as deterministic
is written, describing inventory levels of every item at every FC, and
expected demands at different regions which includes information about items
frequently purchased together in the same order. The objective captures fixed
shipping costs (mostly dependent on the number of distinct FC’s used to
fulfill an order), variable shipping costs (dependent on items and distances),
and shortage costs (dependent on penalties paid for orders not fulfilled). The
LP is then solved, providing a “master plan” of matching supply to demand,
which prescribes for different orders from different regions, how frequently
each FC should be used to fulfill each item in that order. As orders come in
real-time, Jasin and Sinha (2015) randomly dispatch the items to FC’s, making
sure to follow the fulfillment frequencies outlined in the LP’s plan.

Although seemingly uninformed, this randomized fulfillment approach is simple,
fast, and highly parallelizable as it does not require real-time inventory
information across the network once the LP solution is given. Under large
system scales, it also pays variable shipping and shortage costs similar to
what is outlined in the LP. However, fixed costs remain a challenge—the
problem of covering all the items in an order using a small number of distinct
FC’s was already difficult, and the LP’s fulfillment frequencies now impose
additional constraints. Moreover, it has been shown that fixed costs,
capturing the number of boxes from different origins shipped, constitute the
majority of e-commerce fulfillment costs (Xu et al. 2009, Jasin and Sinha
2015), so this presents a major issue. The seminal insight, due to Jasin and
Sinha (2015), is that these frequencies are actually helpful—when using them
to randomly assign an FC to each item, if positive correlation is induced in
the assignments across items, then many items end up assigned to the same FC
and not many distinct FC’s are used. The authors derive an intricate method
for inducing this correlation.

Despite its significance and impact on subsequent work (e.g. Lei et al. 2018,
2021, Zhao et al. 2020), to the best of our knowledge, the correlation method
of Jasin and Sinha (2015) has never been substantially improved, until now.
This paper derives a new correlation method that is intuitively simpler,
computationally faster, and achieves tight performance in two different
regimes.

###  1.1 Correlated Rounding Problem of Jasin and Sinha (2015)

Consider a single order (from a particular region at a particular time)
consisting of $q$ items. For each item in the order, denoted using
$i\in\\{1,\ldots,q\\}$, we are told the fraction of time $u_{ki}$ that it must
be fulfilled from each FC $k\in\\{1,\ldots,K\\}$. Every item must be
fulfilled, so $\sum_{k}u_{ki}=1$ for all $i$. We must randomly choose an FC
for each item $i$ according to these probabilities $u_{ki}$, and an FC is used
if any item is assigned to it (meaning we would ship a box out of that FC).

Intuitively, the goal is to not use many distinct FC’s. This is formalized as
no FC being used with a probability greater than necessary. Specifically, for
each FC $k$, it has to used with probability at least $u_{ki}$ to fulfill any
item $i$, and hence $y_{k}:=\max_{i}u_{ki}$ is a lower bound on its
probability of being used. A method that randomly assigns every item $i$ to an
FC following its marginal probability vector $(u_{ki})_{k=1}^{K}$ is called a
rounding scheme, and the rounding scheme is said to be $\alpha$-competitive if
it uses every FC $k$ with probability at most $\alpha\cdot y_{k}$, for some
$\alpha\geq 1$. Here, $\alpha$ is referred to as the guarantee of the rounding
scheme, which is ideally as small as possible.

A naive rounding scheme is to independently draw an FC for each item. However,
such a random outcome likely uses many distinct FC’s, causing FC’s to be used
more frequently than necessary, and Jasin and Sinha (2015) show that the
guarantee of the independent rounding scheme can be as bad as $\alpha=q$ on a
$q$-item order. Jasin and Sinha (2015) derive an improved rounding scheme that
correlates positively the FC’s drawn across items, so that the random outcome
uses fewer distinct FC’s. They establish that given any $q$ marginal
distributions over FC’s, this correlated rounding scheme is $\approx
q/4$-competitive, improving the guarantee of the naive rounding by a factor of
4.

In this paper we derive two new correlated rounding schemes. The first is
$(1+\ln(q))$-competitive, completely improving the earlier guarantees in terms
of order-dependence on $q$—from linear to logarithmic. The second is
$d$-competitive, where $d$ is a sparsity parameter that describes the maximum
number of options that any item has in terms of where to be fulfilled, i.e.
$d=\max_{i}|\\{k:u_{ki}>0\\}|$. Both of these guarantees are tight for the
correlated rounding problem, as we will show.

#### Implications for dynamic fulfillment.

Our rounding schemes are directly applicable to the original dynamic
fulfillment problem via the approach of Jasin and Sinha (2015). Indeed, each
incoming order can be separately and randomly dispatched, using our choice of
rounding scheme. The results of Jasin and Sinha (2015) then imply that in the
dynamic fulfillment problem, the total cost paid is asymptotically at most
$\beta$ times the optimum, where $\beta$ is a constant that depends on the
average value of $\min\\{1+\ln(q),d\\}$ across orders (different orders have
different sizes $q$ and sparsity parameters $d$, and we can choose the
rounding scheme with the better guarantee between $1+\ln(q)$ and $d$ for each
incoming order). As a special case, if the largest order has size
$\overline{q}$, then the guarantee is $1+\ln(\overline{q})$, matching
computational hardness results for the dynamic fulfillment problem even when
there is a single order. Further details can be found in Section 5.

We note, however, that reducing everything down to the correlated rounding
subroutine is not the only approach to dynamic fulfillment. Indeed, the
correlated rounding problem imposes frequency constraints on every order (that
every item $i$ in every order is assigned to each FC $k$ with marginal
probability exactly $u_{ki}$), with the rationale being that the variable
shipping and inventory shortage costs become relatively inconsequential under
large system scales; unfortunately, this can be restrictive compared to some
alternative approaches, as summarized in Acimovic and Farias (2019).
Nonetheless, this simple and fast approach performs well numerically in
realistic setups, as shown in Jasin and Sinha (2015). In Section 6, we show
using the same setups that our new rounding schemes robustly bolster the
performance of the randomized fulfillment approach, while shortening code and
runtimes. Our code is made publicly available.

###  1.2 Main Idea behind New Rounding Schemes and Analysis

Another benefit of our rounding schemes is that they have a simple
intuition—each FC draws a random “opening time”, and each item is assigned to
the first FC that it sees open under its own, item-specific “time dilation”.
We now describe in detail our two rounding schemes and analysis.

Recall that we are trying to induce positive correlation in the FC’s assigned
across items. To do this, we imagine a process where each FC is initially
closed, and opens at a random time. Items are assigned to the first FC that
they see open. Importantly, each item $i$ views the openings of FC’s on its
own dilated time scale, calibrated so that the probability of it seeing any FC
$k$ open first is exactly $u_{ki}$. Because an FC opening early means that it
will be seen first by more (but not necessarily all) items, this induces
positive correlation in the FC’s assigned across different items.

To make this precise, for each FC $k$, we draw its opening time $E_{k}$
independently from an Exponential distribution with mean $1/y_{k}$, where
$y_{k}:=\max_{i}u_{ki}$. We then define the dilated time scale for an item $i$
as: it sees each FC $k$ open at time $\frac{y_{k}}{u_{ki}}E_{k}$, which we
note is no earlier than $E_{k}$, since $\frac{y_{k}}{u_{ki}}\geq 1$. (If
$u_{ki}=0$, then $\frac{y_{k}}{u_{ki}}E_{k}=\infty$, and item $i$ never sees
FC $k$ open.) The dilated opening times $\frac{y_{k}}{u_{ki}}E_{k}$ are
Exponentially distributed with means
$\frac{y_{k}}{u_{ki}}\cdot\frac{1}{y_{k}}=\frac{1}{u_{ki}}$, and independent
across $k$. Through the lens of Poisson processes, it is easy to see that the
probability of each FC $k$ arriving first into the view of item $i$ is exactly
$\frac{u_{ki}}{u_{1i}+\cdots+u_{Ki}}=u_{ki}$, as desired.

The Poisson lens also helps us upper-bound the probability of an FC $k$
getting used at all. Indeed, since an FC $k$ can only be seen at times later
than $E_{k}$, it can only get used if it arrives when at least one item is
still waiting, an event whose probability is exponentially decaying over time.
Unfortunately, random variable $E_{k}$ is correlated with the latter event,
making the analysis complicated. To fix this, we instead consider a related
process where FC $k$ is “repeatedly opening” following a Poisson process of
rate $y_{k}$, which allows us to exploit the memoryless property and take an
elementary integral to show that the probability of FC $k$ opening is at most
$(1+\ln(q))y_{k}$, completing our sketch of why our first rounding scheme is
$(1+\ln(q))$-competitive.

To motivate our second rounding scheme, we note that the preceding analysis is
poor when $q$ is enormous, because for a long time at least one item will
still be waiting, during which FC openings will result in usage. Therefore, we
consider a modified scheme where each FC $k$ is “forced open” at time
$1/y_{k}$, even if $E_{k}>1/y_{k}$. For each item $i$, it will see each FC $k$
forced open at time
$\frac{y_{k}}{u_{ki}}\cdot\frac{1}{y_{k}}=\frac{1}{u_{ki}}$. Therefore, item
$i$ will get “force-assigned” by time $\frac{1}{\max_{k}u_{ki}}$, and all
items will be force-assigned by time
$\alpha:=\frac{1}{\min_{i}\max_{k}u_{ki}}$, regardless of how many items there
are. Moreover, if $d$ is an upper bound on $|\\{k:u_{ki}>0\\}|$, then
$\max_{k}u_{ki}\geq 1/d$ for all $i$, and hence $\alpha\leq d$. The fact that
all items are assigned by time $d$ w.p. 1 allows us to show that no FC gets
used with probability more than $dy_{k}$.

However, these forced openings cause each item $i$ to be over-fulfilled from
the FC $m(i)$ that it would first see forced open. Therefore, we make a second
modification where for each item $i$, if the over-fulfilled FC $m(i)$ were to
“naturally” open (i.e. $E_{m(i)}<1/y_{m(i)}$), then it is hidden from the view
of item $i$ (until it is forced open) with some likelihood. This likelihood
can be calibrated so that $i$ ends up seeing every FC $k$ open first with
probability exactly $u_{ki}$, as desired.

###  1.3 Further Technical Details and Relationship with Set Cover

We now outline all our new results for the correlated rounding problem and the
related technical results.

  * •

Our main results are a $(1+\ln(q))$-competitive rounding scheme, and a
$d$-competitive rounding scheme (where $d$ denotes the sparsity parameter
$\max_{i}|\\{k:u_{ki}>0\\}|$). These rounding schemes and their analyses are
presented in Section 2.

  * •

The exact guarantee for the rounding scheme of Jasin and Sinha (2015) is given
by a function $B$ of the order size, where $B(q)=\frac{(q+1)^{2}}{4q}$ if $q$
is odd and $B(q)=\frac{q+2}{4}$ if $q$ is even. For small values of $q$, this
is better than our guarantee of $1+\ln(q)$; e.g. if $q=2$ then $B(1)=1$.

  * •

Both of our rounding schemes have a runtime of $O(qK)$. By contrast, the
rounding scheme of Jasin and Sinha (2015) has a runtime of $O(q^{2}K)$,
containing a loop that is quadratic in the number of items $q$.

  * •

If there are only two FC’s, i.e. $K=2$, then a 1-competitive rounding scheme
was recently discovered by Zhao et al. (2020). In this scenario, our second
rounding scheme would only be 2-competitive, since $d=K=2$. However, we
emphasize that parameter $d$ represents the maximum number of distinct FC’s
that hold an item and can generally be much smaller than $K$, whereas their
rounding scheme only works when $K=2$.

  * •

In Section 4, we establish an additional result that computes the optimal
guarantee $\alpha$ and rounding scheme for a given instance, using an LP of
size $O(2^{K})$. Jasin and Sinha (2015) also show how to compute instance-
optimal schemes, using an LP of size $O(K^{q})$. While both are exponentially-
sized, our LP can be applied when $K$ is small; theirs can be applied when $q$
is small.

#### Relating the correlated rounding problem to Set Cover.

  * •

In Section 3, we show that an $\alpha$-competitive rounding scheme implies a
procedure for rounding a fractional Set Cover solution into a randomized
cover, that is feasible w.p. 1, and has no set chosen with probability more
than $\alpha$ times its fractional weight.

  * •

Therefore, we can leverage hardness results from Set Cover to show that an
$\alpha$-competitive rounding scheme must have $\alpha=\Omega(\log(q))$ and
$\alpha\geq d$. The former lower bound establishes our
$(1+\ln(q))$-competitive rounding scheme to be order-optimal in $q$, while the
latter lower bound establishes our $d$-competitive rounding scheme to be
exactly tight in $d$.

  * •

Our $(1+\ln(q))$-competitive rounding scheme also improves guarantees in the
aforementioned randomized rounding problem for Set Cover. To the best of our
knowledge, existing rounding methods for Set Cover take each set with
probability at least $\ln(q)+\omega(1)$ times its fractional weight (Raghavan
and Tompson 1987); see also Motwani and Raghavan (1995) and Vazirani (2001,
Sec 14.2). Although our improvement to $\ln(q)+1$ is only in lower-order
terms, our approach via the correlated rounding problem is both new, and
simpler than many of the commonly-taught methods.

We note that for the Set Cover problem itself, which has nothing to do with
randomization, the Greedy algorithm has a guarantee of $1+1/2+\cdots+1/q$,
which is slightly smaller (better) than our $1+\ln(q)$. Nonetheless, we
believe these connections highlight how the correlated rounding problem is a
harder version of Set Cover—in which a randomized solution, that must satisfy
constraints on how often each set is used to cover each element, is required.
Furthermore, it is interesting to us that a modern problem from e-commerce
practice, identified by Jasin and Sinha (2015), can lead us to improve
randomized rounding schemes for the age-old Set Cover problem from CS theory.

###  1.4 Further Related Work

The dynamic fulfillment problem, and in particular the correlated rounding
approach, is more challenging and relevant in large fulfillment networks.
Fulfillment networks have been getting larger with the advent of omni-channel
retailing, which allows for online orders to be fulfilled from small retail
stores (Acimovic and Farias 2019). Although order sizes have been decreasing
with the advent of fast shipping, online retailers have been making greater
efforts to delay fulfillment and consolidate multiple orders into one before
fulfilling (Wei et al. 2021, Wang et al. 2022). Consequently, the dynamic
fulfillment problem with multi-item orders and flexibility in how to fulfill
them is as relevant as ever (DeValve et al. 2021).

In terms of the overall LP-based approach that justifies the correlated
rounding problem, we should note that LP-based approaches are also heavily
employed in the revenue management literature (see e.g. Talluri and Van Ryzin
2004). They enjoy many benefits such as scalability and ability to incorporate
side constraints, and the given probabilities $u_{ki}$ can always be updated
over time through re-solving (see e.g. Jasin and Kumar 2012) to adjust for
updated inventories and demand predictions over time. An early work advocating
for the LP-based approach in e-commerce fulfillment is Acimovic and Graves
(2015). Very recently, Amil et al. (2022) propose a novel LP that can be used
in place of the standard one, which we discuss at the end of Section 5.

##  2 Formal Specification and Analysis of Rounding Schemes

We recap the correlated rounding problem from the Introduction, our main
object of study.

######  Definition 2.1 (Recap of Problem, Notation, and Terminology)

  * •

An instance of the $\alpha$-competitive rounding scheme problem consists of
$q$ marginal distributions over $K$ FC’s, given by probabilities $u_{ki}$
satisfying $\sum_{k=1}^{K}u_{ki}=1$ for all $i=1,\ldots,q$.

  * •

A rounding scheme must randomly assign each item $i$ to an FC
$Z_{i}\in\\{1,\ldots,K\\}$, satisfying the marginal conditions
$\Pr[Z_{i}=k]=u_{ki}$ for all $i$ and $k$.

  * •

An FC $k$ is used if any item is assigned to it, denoted by the event
$\bigcup_{i=1,\ldots,q}(Z_{i}=k)$, which must occur with probability at least
$y_{k}:=\max_{i}u_{ki}$. Assume without loss that $y_{k}>0$ for all $k$.

  * •

A rounding scheme is $\alpha$-competitive if given any instance, it uses each
FC $k$ with probability at most $\alpha\cdot y_{k}$. The guarantee $\alpha$
can depend on parameters of the instance.

  * •

The sparsity parameter of an instance is defined as
$d=\max_{i}|\\{k:u_{ki}>0\\}|$, the maximum number of distinct FC’s that one
item $i$ could get assigned to.

We now provide efficient algorithmic specifications of our rounding schemes
and analyze them. We believe both our algorithms and proofs to be quite
intuitive, and will frequently provide proof sketches that refer back to the
intuition from Subsection 1.2, where items are waiting for FC’s to open on
their own dilated time scales.

###  2.1 $(1+\ln(q))$-competitive Rounding Scheme

Our rounding scheme is specified in Algorithm 1. Relating back to the
intuitive description, $E_{k}$ is the time at which FC $k$ opens, and
$\frac{y_{k}}{u_{ki}}E_{k}$ is the delayed time (since
$\frac{y_{k}}{u_{ki}}\geq 1$) at which item $i$ sees it open, with
$\frac{y_{k}}{u_{ki}}E_{k}=\infty$ if $u_{ki}=0$. Every item is assigned to
the first FC that it sees open.

Algorithm 1 $(1+\ln(q))$-competitive Rounding Scheme

for $k=1,\ldots,K$ do

$E_{k}\leftarrow$ independent draw from Exponential distribution with mean
$1/y_{k}$

end for

for $i=1,\ldots,q$ do

$Z_{i}\leftarrow\argmin_{k=1,\ldots,K}\frac{y_{k}}{u_{ki}}E_{k}$
$\triangleright$ Break ties arbitrarily

end for

We now prove that Algorithm 1 is a $(1+\ln(q))$-competitive Rounding Scheme,
where $q$ is the number of items. To establish the marginals condition, we use
the interpretation that from the perspective of any individual item, the FC’s
open according to independent Poisson processes.

###### Lemma 2.2

Under Algorithm 1, $\Pr[Z_{i}=k]=u_{ki}$ for all $i=1,\ldots,q$ and
$k=1,\ldots,K$.

###### Proof 2.3

Proof of Lemma 2.2. Consider the perspective of any item $i$. Index $Z_{i}$ is
determined by the smallest realization among
$\\{\frac{y_{k}}{u_{ki}}E_{k}:k=1,\ldots,K\\}$, which are independent
Exponential random variables with means $\\{\frac{1}{u_{ki}}:k=1,\ldots,K\\}$.
Equivalently, $Z_{i}$ is determined by the first arrival among independent
Poisson processes with rates $\\{u_{ki}:k=1,\ldots,K\\}$. By the Poisson
merging theorem, each Poisson process $k$ will be the first to arrive with
probability $\frac{u_{ki}}{u_{1i}+\cdots+u_{Ki}}$, which equals $u_{ki}$ since
$u_{1i}+\cdots+u_{Ki}=1$. Therefore, $\Pr[Z_{i}=k]=u_{ki}$ for all
$k=1,\ldots,K$, completing the proof.

We now prove an intermediate lemma that, intuitively, bounds the probability
of any item $i$ still “waiting” (to be assigned to an FC) up to time $t$,
which can be expressed as the event $(\min_{k}\frac{y_{k}}{u_{ki}}E_{k}\geq
t)$. The final statement then takes a union bound of having any item still
waiting, which intuitively is not too loose since these events are positively
correlated—one item waiting implies that FC’s were late to open, which makes
other items more likely to also be waiting.

###### Lemma 2.4

Under Algorithm 1,
$\Pr[\bigcup_{i=1}^{q}(\min_{k}\frac{y_{k}}{u_{ki}}E_{k}\geq t)]\leq qe^{-t}$
for all $t\geq 0$.

###### Proof 2.5

Proof of Lemma 2.4. First consider any item $i$. Random variables
$\\{\frac{y_{k}}{u_{ki}}E_{k}:k=1,\ldots,K\\}$ are independent and
Exponentially distributed with means $\\{\frac{1}{u_{ki}}:k=1,\ldots,K\\}$.
Therefore, $\min_{k}\frac{y_{k}}{u_{ki}}E_{k}$ is Exponentially distributed
with mean $\frac{1}{u_{1i}+\cdots+u_{Ki}}=1$. Consequently,
$\Pr[\min_{k}\frac{y_{k}}{u_{ki}}E_{k}\geq t]=e^{-t}$, and by the union bound,
$\Pr[\bigcup_{i=1}^{q}(\min_{k}\frac{y_{k}}{u_{ki}}E_{k}\geq t)]\leq qe^{-t}$,
completing the proof.

We are now ready to prove our main result for Algorithm 1. Although technical,
the argument uses a simple intuitive trick. Lemma 2.4 has upper-bounded the
probability of any item still waiting at a time $t$. If an FC $k$ opens at a
time when no item is still waiting, then it is guaranteed to not get used
(since items can only see it open at a delayed time). Unfortunately, the
opening time of an FC $k$ is correlated with the event of having an item still
waiting. To fix this, we imagine FC $k$ as “repeatedly opening” following a
Poisson process of rate $y_{k}$, with it being “used” every time it opens as
long as there is an item still waiting. Since Poisson processes are
memoryless, this now de-correlates the events of FC $k$ opening from the event
of still having an item waiting. Lemma 2.4 can then apply, and the analysis
finishes by taking an integral. The formal proof is presented below.

###### Theorem 2.6

Algorithm 1 is a $(1+\ln(q))$-competitive rounding scheme with runtime
$O(qK)$.

###### Proof 2.7

Proof of Theorem 2.6. The runtime is $O(qK)$ because taking the $\argmin$ over
$k=1,\ldots,K$ for all $i=1,\ldots,q$ is the bottleneck operation in Algorithm
1. Meanwhile, Lemma 2.2 has already shown that the marginals condition is
satisfied. It remains to show that
$\Pr[\bigcup_{i=1,\ldots,q}(Z_{i}=k)]\leq\alpha y_{k}$ for all $k$, with
$\alpha=1+\ln(q)$.

Fix any FC $k$. For all items $i$ with $u_{ki}>0$, event $Z_{i}=k$ can occur
only if $k$ lies in the $\argmin$ in Algorithm 1, i.e. if
$\min_{k^{\prime}}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}}\geq\frac{y_{k}}{u_{ki}}E_{k}$.
We now rewrite this event as follows. Define $S^{1}_{k},S^{2}_{k},\ldots$ to
be the arrival times of a Poisson process of rate $y_{k}$. More specifically,
we will let $S^{1}_{k}=E_{k}$, and $S^{j+1}_{k}$ be the sum of $S^{j}_{k}$
with an independent Exponential random variable of mean $1/y_{k}$, for all
$j\geq 1$. We can derive

$\displaystyle(Z_{i}=k)$
$\displaystyle\subseteq\left(\min_{k^{\prime}}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}}\geq\frac{y_{k}}{u_{ki}}E_{k}\right)$
$\displaystyle=\left(\min_{k^{\prime}\neq
k}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}}\geq\frac{y_{k}}{u_{ki}}S^{1}_{k}\right)$
$\displaystyle=\bigcup_{j=1}^{\infty}\left(\min\left\\{\min_{k^{\prime}\neq
k}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}},\min_{j^{\prime}<j}\frac{y_{k}}{u_{ki}}S^{j^{\prime}}_{k}\right\\}\geq\frac{y_{k}}{u_{ki}}S^{j}_{k}\right)$
(1)

where the final equality (1) holds because the events with $j>1$ never occur
(in particular,
$\min_{j^{\prime}<j}\frac{y_{k}}{u_{ki}}S^{j^{\prime}}_{k}\geq\frac{y_{k}}{u_{ki}}S^{j}_{k}$
is impossible since $S^{j^{\prime}}_{k}<S^{j}_{k}$). The purpose of this
vacuous decomposition is to later relax the event (by decreasing the RHS) and
then apply the memorylessness property of Poisson processes.

We now take a union bound of events (1) over $i$, and analyze the probability
of this union by conditioning on the event that $S^{j}_{k}=t$ for any $j\geq
1$, over all times $t\geq 0$. Formally:

$\displaystyle\Pr\left[\bigcup_{i:u_{ki}>0}\bigcup_{j=1}^{\infty}\left(\min\left\\{\min_{k^{\prime}\neq
k}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}},\min_{j^{\prime}<j}\frac{y_{k}}{u_{ki}}S^{j^{\prime}}_{k}\right\\}\geq\frac{y_{k}}{u_{ki}}S^{j}_{k}\right)\right]$
$\displaystyle=\int_{0}^{\infty}\Pr\left[\bigcup_{i:u_{ki}>0}\left(\min\left\\{\min_{k^{\prime}\neq
k}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}},\min_{j^{\prime}<j}\frac{y_{k}}{u_{ki}}S^{j^{\prime}}_{k}\right\\}\geq\frac{y_{k}}{u_{ki}}t\right)\Bigg{|}\exists
j:S^{j}_{k}=t\right]y_{k}dt$
$\displaystyle\leq\int_{0}^{\infty}\Pr\left[\bigcup_{i:u_{ki}>0}\left(\min\left\\{\min_{k^{\prime}\neq
k}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}},\min_{j^{\prime}<j}\frac{y_{k}}{u_{ki}}S^{j^{\prime}}_{k}\right\\}\geq
t\right)\Bigg{|}\exists j:S^{j}_{k}=t\right]y_{k}dt$
$\displaystyle=\int_{0}^{\infty}\Pr\left[\bigcup_{i:u_{ki}>0}\min_{k^{\prime}=1,\ldots,K}\frac{y_{k^{\prime}}}{u_{k^{\prime}i}}E_{k^{\prime}}\geq
t\right]y_{k}dt$ $\displaystyle\leq
y_{k}\int_{0}^{\infty}\min\\{qe^{-t},1\\}dt$

where the first equality holds because the PDF of the event $(\exists
j:S^{j}_{k}=t)$ takes value $y_{k}$ for all $t$, the first inequality holds
because $\frac{y_{k}}{u_{ki}}\geq 1$, the second equality applies the
memorylessness property of Poisson processes, and the final inequality applies
Lemma 2.4 (along with the trivial upper bound of 1). Note that this analysis
holds for any FC $k=1,\ldots,K$. Therefore, the proof is now completed by
taking an elementary integral:

$\displaystyle\int_{0}^{\infty}\min\\{qe^{-t},1\\}dt$
$\displaystyle=\ln(q)+\int_{\ln(q)}^{\infty}qe^{-t}dt$
$\displaystyle=\ln(q)+qe^{-\ln(q)}$ $\displaystyle=1+\ln(q).$

###### Remark 2.8

Our Algorithm 1 and Theorem 2.6 close the gap that was left open by the
correlated rounding scheme of Jasin and Sinha (2015), whose guarantee grew
linearly (instead of logarithmically) in the number of items $q$. Their scheme
partitions the [0,1] interval and makes the positive correlation in the FC’s
assigned very explicit. By contrast, our rounding schemes are based on a
“trick” of dilating memoryless random variables, and the positive correlation
is implicit. Our trick is designed to facilitate a short analysis, which
closes the gap in the correlated rounding problem.

###  2.2 $d$-competitive Rounding Scheme

Our modified rounding scheme is specified in Algorithm 2. Relating back to the
intuitive description from Subsection 1.2, $m(i)$ is the first FC that item
$i$ would see “forced” open, which it would get assigned to if it was still
unassigned at that point. $X_{ki}$ is a random variable denoting the time at
which item $i$ sees FC $k$ open, which equals $\frac{y_{k}}{u_{ki}}E_{k}$ like
before if $k\neq m(i)$. On the other hand, $X_{m(i),i}$ is upper-bounded by
$1/u_{m(i),i}$, as that is when item $i$ would see FC $m(i)$ forced open. The
final wrinkle is that if FC $m(i)$ were to “naturally” open before it is
forced open, then it needs to be hidden from $i$’s view (until it is forced
open) with some probability, which is indicated by the random variable
$H_{i}$. Finally, every item is assigned to the first FC that it sees open,
after taking into consideration hiding and forced opening.

Algorithm 2 $d$-competitive Rounding Scheme

for $k=1,\ldots,K$ do

$E_{k}\leftarrow$ independent draw from Exponential distribution with mean
$1/y_{k}$

end for

for $i=1,\ldots,q$ do

$m(i)\leftarrow\argmax_{k}u_{ki}$

for $k=1,\ldots,K,\ k\neq m(i)$ do

$X_{ki}\leftarrow\frac{y_{k}}{u_{ki}}E_{k}$

end for

$H_{i}\leftarrow$ independent draw from Bernoulli distribution with mean
$\frac{1-u_{m(i),i}}{1-u_{m(i),i}+u_{m(i),i}e^{1/u_{m(i),i}}-e}$
$\triangleright$ $H_{i}=1$ means FC $m(i)$ is hidden from item $i$ until the
FC is forced open at time $1/y_{m(i)}$

$X_{m(i),i}\leftarrow\frac{y_{m(i)}}{u_{m(i),i}}\min\\{\frac{E_{m(i)}}{1-H_{i}},\frac{1}{y_{m(i)}}\\}$
$\triangleright$ $H_{i}=1$ means $\frac{E_{m(i)}}{1-H_{i}}=\infty$, and hence
$X_{m(i),i}=\frac{1}{u_{m(i),i}}$

$Z_{i}\leftarrow\argmin_{k=1,\ldots,K}X_{ki}$

end for

It can be checked that the probability with which $H_{i}=1$ defined in
Algorithm 2 does indeed lie in $[0,1]$ for all possible values of
$u_{m(i),i}\in(0,1]$. The hiding probability is in fact increasing in
$u_{m(i),i}$, which is intuitive because a larger value of $u_{m(i),i}$
implies an earlier forced opening, suggesting that FC $m(i)$ should be hidden
more often to prevent it from over-fulfilling item $i$. We now prove that this
hiding probability has been calibrated so that the marginals condition is
satisfied exactly.

###### Lemma 2.9

Under Algorithm 2, $\Pr[Z_{i}=k]=u_{ki}$ for all $i=1,\ldots,q$ and
$k=1,\ldots,K$.

###### Proof 2.10

Proof of Lemma 2.9. Fix any item $i$. We show that $\Pr[Z_{i}=k]=u_{ki}$ for
all $k\neq m(i)$, which would automatically imply
$\Pr[Z_{i}=m(i)]=1-\sum_{k\neq m(i)}\Pr[Z_{i}=k]=1-\sum_{k\neq
m(i)}u_{ki}=u_{m(i),i}$. We need to consider two cases: $H_{i}=1$ and
$H_{i}=0$. Hereafter omit index $i$.

First, if $H=1$, then the item does not observe FC $m$ before time $1/u_{m}$.
Therefore, $Z=k$ if and only if $X_{k}$ is the smallest among random variables
$\\{X_{k^{\prime}}:k^{\prime}\neq m\\}$ and also $X_{k}<1/u_{m}$. Recall that
$X_{k^{\prime}}$ is Exponentially distributed with mean $1/u_{k^{\prime}}$ for
all $k^{\prime}\neq m$, and the $X_{k^{\prime}}$’s are independent across
$k^{\prime}$. Therefore, the probability that $\min_{k^{\prime}\neq
m}X_{k^{\prime}}<1/u_{m}$ is equal to the probability that a Poisson process
with rate $\sum_{k^{\prime}\neq m}u_{k^{\prime}}=1-u_{m}$ generates an arrival
before time $1/u_{m}$, which occurs w.p. $1-e^{-(1-u_{m})/u_{m}}$. Conditional
on this, the probability that $\min_{k^{\prime}\neq m}X_{k^{\prime}}=X_{k}$ is
exactly $\frac{u_{k}}{1-u_{m}}$, by the Poisson merging theorem. Therefore,

$\displaystyle\Pr[Z=k|H=1]=(1-e^{-(1-u_{m})/u_{m}})\frac{u_{k}}{1-u_{m}}.$ (2)

Otherwise, if $H=0$, then the item observes all FC’s before time $1/u_{m}$. In
this case, $Z=k$ if and only if $X_{k}$ is the smallest among all random
variables $\\{X_{k^{\prime}}:k^{\prime}=1,\ldots,K\\}$ and also
$X_{k}<1/u_{m}$. By a similar argument as above, the probability that
$\min_{k^{\prime}=1,\ldots,K}X_{k^{\prime}}<1/u_{m}$ is $1-e^{1/u_{m}}$, and
conditional on this, the probability that
$\min_{k^{\prime}=1,\ldots,K}X_{k^{\prime}}=X_{k}$ is $u_{k}$. Therefore,

$\displaystyle\Pr[Z=k|H=0]=(1-e^{1/u_{m}})u_{k}.$ (3)

Let $\eta$ denote $\frac{1-u_{m}}{1-u_{m}+u_{m}e^{1/u_{m}}-e}$, the
probability that $H=1$. Combining (2) and (3), we derive

$\displaystyle\Pr[Z_{i}=k]$
$\displaystyle=\eta(1-e^{-(1-u_{m})/u_{m}})\frac{u_{k}}{1-u_{m}}+(1-\eta)(1-e^{-1/u_{m}})u_{k}$
$\displaystyle=u_{k}\left(1-e^{-1/u_{m}}+\eta\left(\frac{1-e^{-(1-u_{m})/u_{m}}}{1-u_{m}}-(1-e^{-1/u_{m}})\right)\right)$
$\displaystyle=u_{k}\left(1-e^{-1/u_{m}}+\eta\cdot\frac{-e^{-(1-u_{m})/u_{m}}+u_{m}+e^{-1/u_{m}}-u_{m}e^{-1/u_{m}}}{1-u_{m}}\right)$
$\displaystyle=u_{k}\left(1-e^{-1/u_{m}}+e^{-1/u_{m}}\eta\cdot\frac{1-u_{m}+u_{m}e^{1/u_{m}}-e}{1-u_{m}}\right)$
$\displaystyle=u_{k}$

which completes the proof.

We now prove our main result for Algorithm 2. We establish the stronger
guarantee of $\alpha=\frac{1}{\min_{i}\max_{k}u_{ki}}$, which is easily seen
to be at most $d$ since $\max_{k}u_{ki}\geq 1/d$ for all $i$. The proof sketch
is that due to the forced openings, all items are guaranteed to be assigned by
time $\alpha$. Therefore, an FC $k$ can only get used is it opens before time
$\alpha$ (since items can only see it open with a delay), which occurs with
probability no greater than $\alpha y_{k}$.

###### Theorem 2.11

Algorithm 2 is an $\frac{1}{\min_{i}\max_{k}u_{ki}}$-competitive rounding
scheme with runtime $O(qK)$.

###### Proof 2.12

Proof of Theorem 2.11. The runtime is $O(qK)$, because inside the loop for
$i=1,\ldots,q$ in Algorithm 2, there are three bottleneck operations that each
take time $O(K)$: the defining of $m(i)$, the inner loop for $k$, and the
defining of $Z_{i}$. Meanwhile, Lemma 2.9 has already shown that the marginals
condition is satisfied. It remains to show that
$\Pr[\bigcup_{i=1,\ldots,q}(Z_{i}=k)]\leq\alpha y_{k}$ for all $k$, with
$\alpha=\frac{1}{\min_{i}\max_{k^{\prime}}u_{k^{\prime}i}}$.

Fix an FC $k$. If $y_{k}\geq\min_{i}\max_{k^{\prime}}u_{k^{\prime}i}$, then
$\alpha y_{k}\geq 1$ and there is nothing to prove. Therefore, assume
$y_{k}<\min_{i}\max_{k^{\prime}}u_{k^{\prime}i}$, and we must show that
$\Pr[\bigcup_{i=1,\ldots,q}(Z_{i}=k)]\leq\alpha y_{k}$. Since
$y_{k}<\max_{k^{\prime}}u_{k^{\prime}i}$ for all $i$, we know that $k\neq
m(i)$ for all $i$. Thus, we have $X_{ki}=\frac{y_{k}}{u_{ki}}E_{k}$ for all
$i$, and can write

$\displaystyle(Z_{i}=k)$
$\displaystyle\subseteq(\frac{y_{k}}{u_{ki}}E_{k}\leq\min_{k^{\prime}=1,\ldots,K}X_{k^{\prime}i})$
$\displaystyle\subseteq(\frac{y_{k}}{u_{ki}}E_{k}\leq X_{m(i),i})$
$\displaystyle\subseteq(\frac{y_{k}}{u_{ki}}E_{k}\leq 1/u_{m(i),i})$
$\displaystyle=(\frac{y_{k}}{u_{ki}}E_{k}\leq\frac{1}{\max_{k^{\prime}}u_{k^{\prime}i}})$
$\displaystyle\subseteq(\frac{y_{k}}{u_{ki}}E_{k}\leq\alpha)$
$\displaystyle\subseteq(E_{k}\leq\alpha)$

with the final relationship between events holding because
$\frac{y_{k}}{u_{ki}}\geq 1$. Note that the final event is independent of $i$.
Therefore,

$\displaystyle\Pr\left[\bigcup_{i=1,\ldots,q}(Z_{i}=k)\right]\leq\Pr[E_{k}\leq\alpha]=1-e^{-\alpha
y_{k}}$

which is at most $\alpha y_{k}$, completing the proof.

##  3 Connections with Set Cover

In this section we establish our rounding schemes to be order-optimal in terms
of the dependence on $q$ or $d$, by reducing our problem to that of rounding a
fractional solution for Set Cover. We first define the Set Cover problem and
some basic concepts using our language of items and FC’s. We refer to Vazirani
(2001) for further background.

######  Problem 3.1 (Weighted Set Cover)

There are items $i=1,\ldots,q$ to be covered by FC’s $k=1,\ldots,K$. Each FC
$k$ requires a fixed cost of $c_{k}$ to open, and if opened, can cover all
items in a set $U_{k}\subseteq\\{1,\ldots,q\\}$. The objective is to find a
collection of FC’s to open, that covers all the items, and minimizes the sum
of fixed costs paid for opening FC’s. The sparsity of the instance is defined
as $d:=\max_{i}|\\{k:i\in U_{k}\\}|$, the maximum number of different FC’s
that an item $i$ can be covered by.

######  Definition 3.2 (Set Cover Linear/Integer Programs)

The following Integer Program is called the Set Cover IP. In it, binary
variable $y_{k}$ represents FC $k$ being opened. It is an equivalent
formulation of the Weighted Set Cover problem.

$\displaystyle\min\ \sum_{k=1}^{K}c_{k}y_{k}$ $\displaystyle\text{s.t.
}\sum_{k:i\in U_{k}}y_{k}$ $\displaystyle\geq 1$ $\displaystyle\forall
i=1,\ldots,q$ (4) $\displaystyle y_{k}$ $\displaystyle\in\\{0,1\\}$
$\displaystyle\forall k=1,\ldots,K$ (5)

Meanwhile, the Set Cover LP is defined as the relaxation of the Set Cover IP
with constraint (5) changed to $y_{k}\in[0,1]$, for all $K=1,\ldots,K$.

We now define the problem of rounding a fractional solution for Set Cover, in
a way that is analogous to an $\alpha$-competitive rounding scheme, except we
will call it an $\alpha$-competitive “covering” scheme instead.

######  Definition 3.3 ($\alpha$-competitive Covering Scheme)

For $\alpha\geq 1$, an $\alpha$-competitive covering scheme is a method for
constructing random variables $Y_{1},\ldots,Y_{K}\in\\{0,1\\}$ satisfying

$\displaystyle\sum_{k:i\in U_{k}}Y_{k}$ $\displaystyle\geq 1$
$\displaystyle\forall i=1,\ldots,q,\ w.p.~{}1$ (6)
$\displaystyle\mathbb{E}[Y_{k}]$ $\displaystyle\leq\alpha\cdot y_{k}$
$\displaystyle\forall k=1,\ldots,K$ (7)

given any feasible solution $(y_{k})_{k=1}^{K}$ to the Set Cover LP.

We now show that coming up with $\alpha$-competitive rounding schemes is a
harder problem than coming up with $\alpha$-competitive covering schemes.

###### Lemma 3.4

An $\alpha$-competitive rounding scheme can be efficiently applied as an
$\alpha$-competitive covering scheme. Moreover, any dependence of $\alpha$ on
the parameters $q$ or $d$ translate over directly.

###### Proof 3.5

Proof of Lemma 3.4. Take any instance of Set Cover and a feasible solution
$(y_{k})_{k=1}^{K}$ to its LP. For each item $i$, arbitrarily set
$u_{ki}\in[0,y_{k}]$ for each FC $k$ that can cover it, so that $\sum_{k:i\in
U_{k}}u_{ki}=1$. We note that this is always possible since $y_{k}\geq 0$ and
$\sum_{k:i\in U_{k}}y_{k}\geq 1$ by (4). Meanwhile, set $u_{ki}=0$ if $i\notin
U_{k}$.

The marginal distributions $(u_{k1})_{k=1}^{K},\ldots,(u_{kn})_{k=1}^{K}$ now
define an instance for an $\alpha$-competitive rounding scheme, with the same
number of items $q$ and a sparsity $d$ that is no greater than before. We
apply the $\alpha$-competitive rounding scheme that is assumed to exist on
this instance, and define random variables
$Y_{k}=\mathbbm{1}(\bigcup_{i}(Z_{i}=k))$ for all $k=1,\ldots,K$. By the
definition of a rounding scheme, for each item $i$, we know that $Z_{i}=k$ is
true for some index $k\in\\{1,\ldots,K\\}$, with $k\in U_{k}$ since otherwise
$u_{ki}=0$. Therefore, $Y_{k}=1$ for this index $k$ and condition (6) for the
covering scheme is satisfied. Meanwhile, applying the definition of an
$\alpha$-competitive rounding scheme, we have

$\mathbb{E}[Y_{k}]=\Pr\left[\bigcup_{i}(Z_{i}=k)\right]\leq\alpha\cdot\max_{i}u_{ki}\leq
y_{k}.$

We conclude that condition (7) for the covering is satisfied. We also note
that if $\alpha$ depends on the sparsity parameter $d$, then the same
guarantee continues to hold under the old sparsity parameter for Set Cover
which is no less than $d$, completing the proof.

###  3.1 Negative Results for $\alpha$-competitive Rounding Schemes

Equipped with Lemma 3.4, we can now translate hardness results for the
$\alpha$-competitive covering scheme problem into hardness results for the
$\alpha$-competitive rounding scheme problem.

######  Corollary 3.6 (of Lemma 3.4)

An $\alpha$-competitive covering scheme must have $\alpha=\Omega(\log(q))$
(Vazirani 2001, Ex. 13.4). Therefore, an $\alpha$-competitive rounding scheme
must also have $\alpha=\Omega(\log(q))$. Consequently, the
$(1+\ln(q))$-competitive rounding scheme established in Theorem 2.6 achieves
the order-optimal dependence on $q$.

###### Proposition 3.7

An $\alpha$-competitive covering scheme must have $\alpha\geq d$, where $d$
denotes the sparsity of the instance.

###### Proof 3.8

Proof of Proposition 3.7. Consider a Set Cover instance with $d$ fixed, $K$
large, and one item for each subset of $\\{1,\ldots,K\\}$ of size $d$. Each
such item can only be covered by the $d$ FC’s in its corresponding subset,
with the total number of items being $q=\binom{K}{d}$. The sparsity of this
instance is $d$ by definition.

Setting $y_{k}=1/d$ for all $k=1,\ldots,K$ forms a feasible solution to the
Set Cover LP, since $|\\{k:i\in U_{k}\\}|=d$ for all items $i$, and hence LP
constraints (4) are satisfied. On the other hand, any $\alpha$-competitive
covering scheme must set $\sum_{k=1}^{K}Y_{k}>K-d$ w.p. 1, since otherwise
there would be an uncovered item, violating (6). Using the linearity of
expectation, we derive

$K-d\leq\sum_{k=1}^{K}\mathbb{E}[Y_{k}]\leq\sum_{k=1}^{K}\alpha\cdot
y_{k}=K\alpha\frac{1}{d},$

with the second inequality coming from (7). Therefore, $\alpha\geq
d(1-\frac{d}{K}),$ with $\frac{d}{K}$ approaching for arbitrarily large $K$,
completing the proof.

######  Corollary 3.9 (of Lemma 3.4 and Proposition 3.7)

An $\alpha$-competitive rounding scheme must have $\alpha\geq d$.
Consequently, the $d$-competitive rounding scheme established in Theorem 2.11
achieves the optimal (not just order-optimal) dependence on $d$.

##  4 Instance-Optimal Rounding Schemes

The $(1+\ln(q))$-competitive and $d$-competitive rounding schemes discussed in
Sections 2 and 3 were only order-optimal in the worst case. For a particular
instance given by $q$ marginals over $\\{1,\ldots,K\\}$, one could also
consider the problem of computing the maximum guarantee $\alpha$ and rounding
scheme that satisfies the marginal frequency constraints.

We formulate this problem using an LP with the following variables. For all
subsets $S$ of the FC’s $\\{1,\ldots,K\\}$, let $z(S)$ denote the probability
that exactly the set of FC’s in $S$ get used. For all
$S\subseteq\\{1,\ldots,K\\}$, FC’s $k\in S$, and items $i$, let $u_{ki}(S)$
denote the probability that the set of FC’s in $S$ get used and that item $i$
is fulfilled from FC $k\in S$. The problem of minimizing $\alpha$ in an
$\alpha$-competitive rounding scheme for this particular instance can then be
formulated as

$\displaystyle\min\ \alpha$ (8) $\displaystyle\text{s.t. }\sum_{k\in
S}u_{ki}(S)$ $\displaystyle=z(S)$ $\displaystyle\forall S,i=1,\ldots,q$ (9)
$\displaystyle\sum_{S}u_{ki}(S)$ $\displaystyle=u_{ki}$ $\displaystyle
k=1,\ldots,K,i=1,\ldots,q$ (10) $\displaystyle\sum_{S\ni k}z(S)$
$\displaystyle\leq\alpha\cdot y_{k}$ $\displaystyle\forall k=1,\ldots,K$ (11)
$\displaystyle\sum_{S}z(S)$ $\displaystyle=1$ (12) $\displaystyle z(S)$
$\displaystyle\geq 0$ $\displaystyle\forall S$ (13) $\displaystyle u_{ki}(S)$
$\displaystyle\geq 0$ $\displaystyle\forall S,k\in S,i=1,\ldots,q$ (14)

where constraints (9) enforce that every item $i$ must be fulfilled from
exactly one FC on each subset $S$, constraints (10) and (11) enforce the
marginal and $\alpha$-competitive properties of a rounding scheme, constraints
(12)–(13) enforce that exactly one subset $S$ is selected, and last but not
least, (14) ensures that there is only a variable $u_{ki}(S)$ if $k\in S$.

Our LP has size $O(nK2^{K})$, which is exponential in $K$ but tractable if $K$
is a fixed constant. Jasin and Sinha (2015) derive an exponential-sized LP for
the same purpose, except instead there is a variable for every possible
mapping from $\\{1,\ldots,q\\}$ to $\\{1,\ldots,K\\}$, for which there are
$K^{q}$ possibilities. Our LP’s are more practical in situations where $K$ is
small but $q$ is large, which is the case in the application of e.g. Zhao et
al. (2020).

##  5 $\alpha$-competitive Rounding Scheme applied to Dynamic Fulfillment

In this section we recap the general dynamic fulfillment problem from Jasin
and Sinha (2015), and formalize the implication of our $\alpha$-competitive
rounding schemes for the overall problem.

#### Problem definition.

There is a horizon consisting of time steps $t=1,\ldots,T$, during which items
$i=1,\ldots,n$ are fulfilled from FC’s $k=1,\ldots,K$. Each item $i$ starts
with $b_{ki}$ units of inventory at each FC $k$, with the end of the horizon
representing the time at which inventories are replenished again. Orders come
from one of regions $j=1,\ldots,J$, and are described by a subset111 This
section introduces the broader problem with $n$ items in the universe and
orders $a$ which are subsets of $\\{1,\ldots,n\\}$. The earlier Sections 2, 3
and 4 are applied by focusing on a single order $a$, letting $q:=|a|$, and
renumbering the items in $a$ to be $1,\ldots,q$, ignoring all other items.
Generally in e-commerce fulfillment, $n$ can be much larger than $q$. of items
$a\subseteq\\{1,\ldots,n\\}$ that was just purchased. During each time step,
up to one order arrives, which is from region $j$ and is for subset $a$ with
probability $\lambda^{a}_{j}$, with $\sum_{a,j}\lambda^{a}_{j}\leq 1$. As is
standard in revenue management, we assume a granular division of time such
that at most one order can arrive during each time step. Also, as justified in
Jasin and Sinha (2015), we assume that orders cannot contain more than one of
any item, and assume a small universe of possible subsets $a$. We let
$c^{\mathrm{unit}}_{kij}$ denote the variable cost of fulfilling one unit of
item $i$ from FC $k$ to location $j$, and let $c^{\mathrm{fixed}}_{kj}$ denote
the fixed cost of sending a package (containing one or more items) from FC $k$
to location $j$.

The goal is to dynamically decide the FC’s to use to fulfill the items in each
order that arrives over the time horizon, to minimize total expected cost.
Note that if an FC $k$ is used to fulfill a subset $a^{\prime}\subseteq a$ of
an order from a location $j$, then the cost required to send that package is
$c^{\mathrm{fixed}}_{kj}+\sum_{i\in a^{\prime}}c^{\mathrm{unit}}_{kij}$. All
items in each arriving order must be fulfilled from some FC, where we assume
the existence of a null FC 0 with infinite inventory so that this is always
feasible, with $c^{\mathrm{unit}}_{0ij}$ denoting the “shortage” cost of
failing to fulfill one unit of item $i$ to region $j$.

#### LP benchmark.

Solving for the optimal dynamic fulfillment policy using dynamic programming
is intractable, since the state space is exponential in the number of items.
Thus, the following “deterministic” LP benchmark222This is identical to the
linear program defining $\tilde{J}_{DLP}$ (Jasin and Sinha 2015, p. 1340),
except we have let $u^{a}_{kij}$ and $y^{a}_{kj}$ represent their variables
$U^{a}_{kij}$ and $Y^{a}_{kj}$ divided by $T\lambda^{a}_{j}$, respectively. is
often used to derive heuristic policies and bound their suboptimality relative
to the optimal dynamic programming policy.

$\displaystyle\mathsf{DLP}:=\min\ \sum_{a,k,j}T\lambda^{a}_{j}\left(\sum_{i\in
a}c^{\mathrm{unit}}_{kij}u^{a}_{kij}+c^{\mathrm{fixed}}_{kj}y^{a}_{kj}\right)$
$\displaystyle\text{s.t. }\sum_{j}\sum_{a\ni i}T\lambda^{a}_{j}u^{a}_{kij}$
$\displaystyle\leq b_{ki}$ $\displaystyle\forall k,i$
$\displaystyle\sum_{k}u^{a}_{kij}$ $\displaystyle=1$ $\displaystyle\forall
a,j,i\in a$ $\displaystyle y^{a}_{kj}\geq u^{a}_{kij}$ $\displaystyle\geq 0$
$\displaystyle\forall a,k,j,i\in a$

In the linear program defining $\mathsf{DLP}$, for any subset $a$ of items
ordered from any region $j$, variable $u^{a}_{kij}$ represents the proportion
of times item $i\in a$ should be fulfilled from FC $k$, with constraint
$\sum_{k}u^{a}_{kij}=1$ for each such item $i$ in the order. Meanwhile,
variable $y^{a}_{kj}$ represents the probability that a FC $k$ would have to
be used at all, which is constrained to be at least $u^{a}_{kij}$ for any
single item $i\in a$. Note that in an optimal solution we can always assume
$y^{a}_{kj}=\max_{i\in a}u^{a}_{kij}$ for all $a,k,j$. These variables
$u^{a}_{kij}$ and $y^{a}_{kj}$ correspond to our variables $u_{ki}$ and
$y_{k}$ from earlier, where we had dropped scripts $a,j$ to focus on a single
multi-item order from a single region.

Moreover, the first constraint enforces that the expected number of times any
FC $k$ fulfills any item $i$ (to any region $j$, as part of any subset $a$
containing $i$) does not exceed its starting inventory $b_{ki}$. Finally, the
objective value defining $\mathsf{DLP}$ represents the total expected cost of
the LP benchmark over the time horizon, accounting for unit costs, fixed
costs, as well as shortage costs (recalling that there is a null FC $k=0$).
This interpretation of $\mathsf{DLP}$ intuitively leads to the following
lemma.

######  Lemma 5.1 (Jasin and Sinha (2015))

For any instance of the problem, the expected cost paid by any dynamic
fulfillment policy must be at least the value of $\mathsf{DLP}$ for that
instance.

#### Randomized fulfillment algorithm and reduction result.

In light of the interpretation of the linear program defining $\mathsf{DLP}$
above, Jasin and Sinha (2015) also use it to derive the following randomized
fulfillment heuristic. First, we solve the LP, hereafter using
$u^{a}_{kij},y^{a}_{kj}$ to refer to a fixed optimal solution. At each time
step $t=1,\ldots,T$, if an order for subset $a$ comes from region $j$, the
heuristic policy randomly chooses an FC $k$ to fulfill each item $i\in a$
according to probabilities $u^{a}_{kij}$, independently across time steps,
without adapting at all to the remaining inventory. If the chosen FC for an
item has stocked out, then that item is simply not fulfilled (i.e. the null FC
is used).

This randomized fulfillment heuristic that does not rely on real-time
inventory information has been shown to perform well asymptotically, although
its theoretical guarantee depends on how exactly FC’s are chosen to fulfill
items during each time step, namely, the $\alpha$-competitive rounding scheme
that is used. Jasin and Sinha (2015) show that the unit and shortage costs
paid by the randomized fulfillment heuristic is asymptotically optimal
relative to the $\mathsf{DLP}$, but the bottleneck is the fixed costs, where
every time an order for subset $a$ comes from region $j$ (regardless of
asymptotics) the cost paid could be $\alpha$ times as much as the
$\mathsf{DLP}$. Here $\alpha$ depends on $a$ and $j$, and using the correlated
rounding schemes from Theorems 2.6 and 2.11 in this paper in conjunction with
the results from Jasin and Sinha (2015) we can always guarantee an
$\alpha$-competitive rounding scheme where

$\displaystyle\alpha=\min\Big{\\{}1+\ln(|a|),(\min_{i\in
a}\max_{k}u^{a}_{kij})^{-1},B(|a|)\Big{\\}}$ (15)

and $B(\cdot)$ is the function from Jasin and Sinha (2015).

Jasin and Sinha (2015) show that the asymptotic cost paid by the randomized
fulfillment heuristic relative to $\mathsf{DLP}$, assuming it chooses the
correlated rounding scheme corresponding to the smallest argument in (15)
whenever any subset $a$ is ordered from any region $j$, is a weighted average
of expression (15) over $a$ and $j$. To formally state this result, we need to
finally define what “asymptotic” means. Here, one considers a scaling regime
where for any fixed instance and any $\theta\geq 0$, the “scaled instance” is
defined to the the one where the horizon length $T$ has been replaced by
$\theta T$ while each starting inventory $b_{ki}$ has also been replaced by
$\theta b_{ki}$. Let $\mathsf{DLP}(\theta)$ denote the optimal objective value
$\mathsf{DLP}$ on the instance scaled by $\theta$, and let
$\mathsf{ALG}(\theta)$ denote the expected cost paid by the randomized
fulfillment heuristic on the same scaled instance. The following is then
implied by the proof of Theorems 1 and 2 from Jasin and Sinha (2015) (see
Jasin and Sinha (2015, p. ec5)), combined with our discussion above.

######  Theorem 5.2 (Jasin and Sinha (2015))

In the multi-item e-commerce fulfillment problem,

$\displaystyle\lim_{\theta\to\infty}\frac{\mathsf{ALG}(\theta)}{\mathsf{DLP}(\theta)}\leq\frac{\sum_{a,k,j}\lambda^{a}_{j}c^{\mathrm{fixed}}_{kj}y^{a}_{kj}\min\Big{\\{}1+\ln(|a|),(\min_{i\in
a}\max_{k^{\prime}}u^{a}_{k^{\prime}ij})^{-1},B(|a|)\Big{\\}}}{\sum_{a,k,j}\lambda^{a}_{j}c^{\mathrm{fixed}}_{kj}y^{a}_{kj}}.$
(16)

Since any fulfillment policy must pay cost at least $\mathsf{DLP}(\theta)$ by
Lemma 5.1, this shows that the randomized fulfillment heuristic cannot be
worse than the optimal dynamic program by a factor greater than the RHS of
(16). The RHS of (16) is a weighted average of the minimum of the guarantees
from three different rounding schemes, and was referred to as $\beta$ in the
Introduction. In order to achieve this, the randomized fulfillment heuristic
must choose for every incoming order $a$ the rounding scheme with the best
guarantee among that of Jasin and Sinha (2015), and our two new ones. Simpler
bounds can also be derived by relaxing the RHS of (16); e.g.

$\displaystyle\lim_{\theta\to\infty}\frac{\mathsf{ALG}(\theta)}{\mathsf{DLP}(\theta)}\leq\frac{\sum_{a,k,j}\lambda^{a}_{j}c^{\mathrm{fixed}}_{kj}y^{a}_{kj}\Big{(}1+\ln(|a|)\Big{)}}{\sum_{a,k,j}\lambda^{a}_{j}c^{\mathrm{fixed}}_{kj}y^{a}_{kj}}\leq\frac{\sum_{a,k,j}\lambda^{a}_{j}c^{\mathrm{fixed}}_{kj}y^{a}_{kj}\max_{a^{\prime}}\Big{\\{}1+\ln(|a^{\prime}|)\Big{\\}}}{\sum_{a,k,j}\lambda^{a}_{j}c^{\mathrm{fixed}}_{kj}y^{a}_{kj}}=1+\ln(\max_{a^{\prime}}|a^{\prime}|).$
(17)

Jasin and Sinha (2015, Thm. 2) prove the same guarantee as Theorem 5.2 except
with the $\min\\{\cdot\\}$ replaced by just $B(|a|)$, while Zhao et al. (2020)
prove the same result where the upper bound on the RHS is 1 (i.e. prove
asymptotic optimality) if there are only two FC’s in the network. We emphasize
that all of these asymptotic guarantees which have eliminated the unit and
shortage costs only hold if the LP inventory constraints are satisfied in
expectation at every time step, justifying why all of these papers study
correlated rounding schemes.

Finally, we argue that the corollary of Theorem 5.2 depicted in (17), arising
from the $(1+\ln(|a|))$-competitive rounding scheme in our paper, is in fact
tight. In Section 3 we had already shown that $1+\ln(|a|)$ is the best-
possible guarantee for the correlated rounding problem, but here we show
computational hardness for dynamic fulfillment, again through a reduction to
Set Cover.

###### Proposition 5.3

For any positive integer $q$, it is NP-hard to solve dynamic fulfillment using
total cost less than $(1-o(1))\ln(q)$ times the optimal cost (given by a
computationally-unconstrained dynamic program), even if all orders have size
$q$ and even on the scaled instance as $\theta\to\infty$.

###### Proof 5.4

Proof of Proposition 5.3. Given any instance of (unweighted) Set Cover, as
defined in 3.1, we show how it can be represented by an instance of the
dynamic fulfillment problem, as defined in this section. Recall that $q,K$
were the number of items, sets respectively in the Set Cover problem. Consider
a dynamic fulfillment problem with base time horizon $T=1$, one region, a
deterministic order type $a$ of size $q$, and $K$ FC’s. All unit shipping
costs are 0 and fixed shipping costs are 1. Starting inventory $b_{ki}$ equals
1 if $i\in U_{k}$, and 0 otherwise. Let $\theta$, the positive integer by
which both the time horizon and starting inventories are scaled, be arbitrary.

Due to the inventory configuration, an item $i$ can only be feasibly assigned
to an FC $k$ if $i\in U_{k}$, i.e. if item $i$ was covered by set $k$. The
assignment of an item $i$ to any feasible FC $k$ that is already being used
(i.e. whose fixed shipping cost is being paid) is irrelevant, since all such
FC’s would start with $\theta$ units of item $i$ and the inventory constraint
is not binding. Therefore, the decision at every period in the dynamic
fulfillment problem is identical and equivalent to the minimization problem of
the given Set Cover instance, where the goal is to choose a minimum set of
FC’s to use such that each of the $q$ items in the order can be assigned. The
objective functions also coincide.

Therefore, if it were possible to solve dynamic fulfillment using total cost
less than $(1-o(1))\ln(q)$ times the optimum, then it would be possible to
solve Set Cover using total cost less than $(1-o(1))\ln(q)$ times the optimum.
By Dinur and Steurer (2014), the latter statement would imply that P=NP. Since
the scaling parameter $\theta$ was arbitrary, the proof is now complete.

###### Remark 5.5

Very recently, Amil et al. (2022) propose an eye-opening approach to the
dynamic fulfillment problem that still uses the randomized fulfillment
heuristic but solves a bigger LP that is tighter than $\mathsf{DLP}$. This
bigger LP explicitly models the different “methods” by which the items in an
order can be split across FC’s and fulfilled, obfuscating the need for a
correlated rounding scheme. The authors show that the value of
$\mathsf{ALG}(\theta)$ relative to their LP approaches 1 as $\theta\to\infty$,
achieving asymptotic optimality and seemingly contradicting Proposition 5.3.
However, generally there could be exponentially many ways to split a $q$-item
order across $K$ FC’s, so without restrictions on the methods, their LP cannot
be solved in polynomial time (unless P=NP). Therefore, in unrestricted
settings with large orders, solving the smaller LP and using our correlated
rounding procedure is still highly relevant.

##  6 Numerical Study

We test our $\alpha$-competitive rounding schemes on the general multi-item
dynamic fulfillment problem formalized in Section 5. We construct instances
aimed to model the operations of a large e-tailer in the continental United
States, following the setup of Jasin and Sinha (2015) as closely as possible.
Our code is in Julia, uses the JuMP (Dunning et al. 2017) package, and is made
publicly available at
https://github.com/Willmasaur/multi_item_e_commerce_fulfillment.

#### Regions, fulfillment centers, costs.

We allow orders to arrive from regions corresponding to the $99$ largest
metropolitan areas in the U.S., excluding Honolulu, HI. The arrival rate from
each region is scaled by its 2022 population according to the US Cities
Database on https://simplemaps.com/data. Meanwhile, we take the $10$ largest
Amazon.com Inc. fulfillment centers that were operational333Compiled from the
information at https://www.mwpvl.com/html/amazon_com.html; available with our
code.  as of 2015 and assume all items are shipped from one of these
centralized FC’s. Following Jasin and Sinha (2015), the fixed cost of
packaging a box at any FC $k$ for any region $j$ is
$c^{\mathrm{fixed}}_{kj}=8.759$, while the cost of shipping a single item $i$
from any FC $k$ to any region $j$ is
$c^{\mathrm{unit}}_{kij}=0.423+0.000541\mathsf{dist}_{kj}$, where
$\mathsf{dist}_{kj}$ is the air distance between FC $k$ and region $j$ in
miles. Not fulfilling an item $i$ costs double the maximum distance; see Jasin
and Sinha (2015) for details.

We note that our city populations and FC locations may differ from Jasin and
Sinha (2015), as the exact sources they cited are no longer publicly
available. We also procedurally diverge from Jasin and Sinha (2015) by always
selecting the largest cities and fulfillment centers, whereas they select
randomly when fewer than 99 cities or fewer than 10 FC’s are needed. We
believe this to generate a more interesting smaller network, because the 10
largest cities are spread out across the corners while the 5 FC’s are located
in the middle, resulting in difficult fulfillment decisions where a city can
be “nearby” to multiple FC’s (see the data files provided with our code for
details).

#### Order types, demand rates, starting inventories.

Order types $a$ each denote a subset of size up to $n_{\mathrm{max}}$, from a
universe of $n$ items. For each size in $1,\ldots,n_{\mathrm{max}}$, there are
$n_{\mathrm{per}}$ fixed order types, each of which is a subset of the $n$
items drawn uniformly at random with the correct size. There is also an order
type with size 0, which represent the lack of a customer arrival at a time
step. Note that the total number of order types is
$1+n_{\mathrm{max}}n_{\mathrm{per}}$, which we denote using $Q$.

The demand probabilities are first split randomly between the order sizes
$0,1,\ldots,n_{\mathrm{max}}$, and then for each size, split randomly between
the types with that size. This yields a $Q$-dimensional probability vector,
i.e. a vector whose entries are non-negative and sum to 1. Then, a
$QJ$-dimensional probability vector is constructed by further splitting each
order type among the metropolitan areas according to their populations. This
vector $(\lambda^{a}_{j})_{a,j}$ is then used as input for the dynamic
fulfillment problem.

Finally, to determine starting inventories, each FC $k$ first randomly decides
whether to carry each item $i$, independently with probability
$p_{\mathrm{carry}}$. Then, for each region $j$, the closest FC $k$ that
carries each item $i$ is identified as $\mathsf{closest}_{i,j}$. For an item
$i$, its “demand” at an FC $k$ is

$\displaystyle\mathsf{dem}_{k,i}=\sum_{a\ni
i}\sum_{j}\mathbbm{1}(\mathsf{closest}_{i,j}=k)\cdot\lambda^{a}_{j},$

where we sum over all queries $a$ containing a copy of item $i$, and consider
only the regions $j$ for which FC $k$ is identified as the closest when
summing over arrival probabilities $\lambda^{a}_{j}$. Given these values,
starting inventories are then placed so that
$b_{ki}=T\mathsf{dem}_{k,i}+z_{\mathrm{safety}}\sqrt{T\mathsf{dem}_{k,i}(1-\mathsf{dem}_{k,i})}$
for all $k$ and $i$, where we note that the total demand for item $i$ closest
to FC $k$ over $T$ time steps is Binomially distributed, with mean
$T\mathsf{dem}_{k,i}$ and variance
$T\mathsf{dem}_{k,i}(1-\mathsf{dem}_{k,i})$. The formula for $b_{ki}$ is the
ideal inventory level to start with according to a Newsvendor model, with
safety stock multiplier $z_{\mathrm{safety}}$ set to 0.5 for all items.

We note that our procedures for randomly generating order types, demand rates,
and carrying decisions follow Jasin and Sinha (2015, EC.3) exactly, in which
these methods are justified. The details of these methods can also be found in
our code.

#### Algorithms.

Like Jasin and Sinha (2015), we test the Myopic fulfillment policy as a
baseline, which fulfills each item from the closest FC that carries it, not
accounting for split orders and minimizing the number of boxes shipped. We
then consider four different algorithms following the randomized fulfillment
heuristic described in Section 5:

  * •

Indep: Independent Rounding, as described in Jasin and Sinha (2015);

  * •

JS: Correlated Rounding scheme of Jasin and Sinha (2015) based on line
partitions;

  * •

Dilate: $(1+\ln(|a|))$-competitive scheme based on dilated opening times
(Subsection 2.1);

  * •

ForceOpen: $d$-competitive scheme based on dilated times and forced openings
(Subsection 2.2).

Jasin and Sinha (2015) compare Indep and JS to the Myopic fulfillment policy;
we additionally compare our new correlated rounding schemes Dilate and
ForceOpen.

###  6.1 Experimental Setups

We consider two experimental setups. First, in Subsection 6.2, we let the
number of regions, FC’s, items, and time steps be $J=10,K=5,n=20,T=10^{5}$
respectively. The queries and starting inventories are generated with
$n_{\mathrm{max}}$ varying in $\\{2,5,10\\}$, $n_{\mathrm{per}}$ fixed to 5,
and $p_{\mathrm{carry}}$ fixed to 0.75. We note that when $n_{\mathrm{max}}=5$
this is exactly the “base case” simulated in Jasin and Sinha (2015). We vary
$n_{\mathrm{max}}$ to see how different rounding schemes handle different
order sizes.

We consider a bigger network in Subsection 6.3, where the number of regions,
FC’s, and items are $J=99,K=10,n=100$ respectively. These represent the
largest values considered in Jasin and Sinha (2015), and we also increase $T$
to $10^{6}$ to better capture asymptotic performance. The queries are
generated with $n_{\mathrm{max}}$ and $n_{\mathrm{per}}$ increased to 10.
Meanwhile, we vary $p_{\mathrm{carry}}$ in $\\{0.25,0.5,0.75\\}$ to
investigate how in a big sparse network with a small value
$p_{\mathrm{carry}}$, the problem can still be easy and in particular
ForceOpen can perform well because $d$ is small.

For each experimental setup, we randomly generate 30 instances, and then
randomly generate 30 arrival sequences for each instance. We use the same
arrival sequences for every algorithm to minimize the discrepancy caused by
variance in arrival sequences. We fix $z_{\mathrm{safety}}$ to be 0.5
throughout our experiments. All of these aspects match what is done in Jasin
and Sinha (2015).

###  6.2 Performance on Smaller Network with varying Order Size

We consider the first experimental setup with the smaller network, generating
30 random instances for each value of $n_{\mathrm{max}}$ in $\\{2,5,10\\}$.
For each instance, we consider the benchmark $\mathsf{DLP}$ described in
Section 5 which is a lower bound on the cost of any fulfillment algorithm. We
draw 30 arrival sequences to test the performance of the 5 specific algorithms
discussed earlier, and compute the average cost of each algorithm over these
30 arrival sequences. We consider how much greater this average cost is than
the value of $\mathsf{DLP}$ for that instance, expressed as a percentage. The
average of these “loss” percentages over the 30 instances are then reported in
Table 1, for each algorithm. We also report the average runtime444See our code
for the exact timing functions used. The time (in seconds) was measured on a
Dell Latitude 5510 laptop with an Intel(R) Core(TM) i7-10810U CPU @ 1.10GHz
processor and 32GB of RAM. of each algorithm, which we note is the total
runtime used to evaluate the 30 arrival sequences for an instance, averaged
over instances. Finally, we report for each algorithm the average number of
FC’s used per order (not counting the “null” FC 0).

Table 1: Performance and runtime metrics for the 5 different algorithms under the 3 different values of $n_{\mathrm{max}}$. The best (smallest) performances are bolded for each row. | Myopic | Indep | JS | Dilate | ForceOpen
---|---|---|---|---|---
$n_{\mathrm{max}}=2$ Avg. Loss | 4.3% | 3.1% |  2.3% | 2.4% | 2.4%
$n_{\mathrm{max}}=5$ Avg. Loss | 12.9% | 14.9% | 9.3% |  8.3% | 8.9%
$n_{\mathrm{max}}=10$ Avg. Loss | 17.7% | 16.5% | 11.7% |  8.6% | 9.4%
$n_{\mathrm{max}}=2$ Runtime per Instance | 0.33s | 0.38s | 1.17s | 0.39s | 0.43s
$n_{\mathrm{max}}=5$ Runtime per Instance | 0.52s | 0.59s | 3.37s | 0.62s | 0.72s
$n_{\mathrm{max}}=10$ Runtime per Instance | 0.84s | 1.03s | 9.12s | 1.09s | 1.32s
$n_{\mathrm{max}}=2$ Avg. FC’s per Order | 0.68 | 0.67 | 0.66 | 0.66 | 0.66
$n_{\mathrm{max}}=5$ Avg. FC’s per Order | 1.29 | 1.22 | 1.16 | 1.15 | 1.16
$n_{\mathrm{max}}=10$ Avg. FC’s per Order | 1.73 | 1.6 | 1.51 | 1.44 | 1.46

#### Observations from results in Table 1.

Our algorithms perform favorably in comparison to Myopic, Indep, and JS.
Indeed, they pay marginally more cost than JS when $n_{\mathrm{max}}=2$, and
overtake JS as soon as $n_{\mathrm{max}}=5$, i.e. orders have sizes between 1
and 5. This is surprising in that the theoretical guarantee of JS is better
for the values of $n$ in this range. Similar improvements are observed in
terms of the average number of FC’s used per order. Also, we note that the
losses of 8.3% and 8.6% for Dilate are relative to an (unreasonable) LP
benchmark which does not face any stochastic fluctuation; the loss relative to
an actual fulfillment policy that can be implemented (e.g., the optimal
dynamic programming policy, given the exponential time required to compute it)
would be much smaller. For this reason, we consider the numbers in Table 1
more useful for comparing algorithms than for evaluating absolute performance.

A further, perhaps more salient feature of our algorithms is their simplicity
and interpretability. As evidenced in our code, the rounding scheme in Dilate
(Algorithm 1) takes 10 lines to write, whereas the rounding scheme in JS took
us 100 lines. Also, the average runtime per instance for Dilate is better than
JS by a factor of 5–10. This seemingly innocuous difference on the smaller
network becomes more pronounced on the bigger network, as we see next.

###  6.3 Performance on Bigger Network with varying Fulfillment Flexibility

We consider the second experimental setup described in Subsection 6.1. We
report average losses and runtimes for each of the 5 algorithms, in the same
way as defined in Subsection 6.2. We generate 30 random instances for each
value of $p_{\mathrm{carry}}$ in $\\{0.25,0.5,0.75\\}$ and report the averages
in Table 2.

We note that $p_{\mathrm{carry}}$ is a measure of fulfillment flexibility, in
that a higher value of $p_{\mathrm{carry}}$ leads to more FC’s being able to
fulfill each item and hence more flexibility in the network. Generally this
results in a harder fulfillment problem, with a larger value of $d$, which we
recall denotes the maximum number FC’s carrying any item. A lower value of
$p_{\mathrm{carry}}$, on the other hand, results in a smaller $d$ and a better
guarantee for ForceOpen.

Table 2:  Performance and runtime metrics for the 5 different algorithms under the 3 different values of $p_{\mathrm{carry}}$. The best (smallest) performances are bolded for each row. | Myopic | Indep | JS | Dilate | ForceOpen
---|---|---|---|---|---
$p_{\mathrm{carry}}=0.25$ Avg. Loss | 34.8% | 10.2% | 7.6% | 5.6% |  5.3%
$p_{\mathrm{carry}}=0.50$ Avg. Loss | 26.7% | 23.4% | 17.7% |  12.6% | 13.1%
$p_{\mathrm{carry}}=0.75$ Avg. Loss | 22.3% | 34.2% | 23.2% |  16.1% | 17.7%
$p_{\mathrm{carry}}=0.25$ Runtime per Instance | 11.23s | 15.43s | 162.31s | 14.24s | 16.88s
$p_{\mathrm{carry}}=0.50$ Runtime per Instance | 11.89s | 18.25s | 162s | 17.01s | 19.25s
$p_{\mathrm{carry}}=0.75$ Runtime per Instance | 13.01s | 19.33s | 169.27s | 18.59s | 22.09s
$p_{\mathrm{carry}}=0.25$ Avg. FC’s per Order | 3.22 | 1.31 | 1.27 | 1.22 | 1.24
$p_{\mathrm{carry}}=0.50$ Avg. FC’s per Order | 2.4 | 1.98 | 1.87 | 1.76 | 1.78
$p_{\mathrm{carry}}=0.75$ Avg. FC’s per Order | 1.71 | 1.79 | 1.62 | 1.50 | 1.53

#### Observations from results in Table 2.

In this bigger network which also has larger order sizes, all algorithms
perform worse. Myopic performs particularly poorly with large order sizes,
because it will likely always split the order (since not all FC’s stock all
items). We can see a greater separation between the performance of our
algorithms, Dilate and ForceOpen, vs. the performance of the other algorithms.
And while we had always observed ForceOpen to both be more complex and perform
slightly worse than Dilate, we now see that when $p_{\mathrm{carry}}=0.25$, it
in fact performs better. This is related to its theoretical guarantee—the
value of $d$ tends to be smaller when $p_{\mathrm{carry}}=0.25$, because each
item in expectation is carried in only 2.5 FC’s.

There is also now a factor-10 speedup in the runtime of our algorithms
compared to JS, which means that the time to finish per instance is on the
order of tens of seconds instead of minutes.

#### Takeaways from numerical study.

Under the randomized fulfillment heuristic of Jasin and Sinha (2015), one
should generally default to Dilate to perform correlated rounding, because it
is simple to implement, fast to run, and performs either the best or close to
the best across the different setups. For orders with 2 items, JS may perform
slightly better. In large sparse networks where each item is carried at very
few FC’s, ForceOpen may perform slightly better.

##  7 Conclusion

We provide the first improvements to the celebrated correlated rounding
procedure of Jasin and Sinha (2015) for the problem of multi-item e-commerce
order fulfillment. We derive rounding schemes with guarantees of $1+\ln(q)$
and $d$ respectively, where $q$ is the number of items in the order and $d$ is
the maximum number of fulfillment centers containing any item. The first of
these guarantees improves the guarantee of $\approx q/4$ from Jasin and Sinha
(2015) by an order of magnitude, in terms of the dependence on $q$. We also
show both of our guarantees to be tight, by deriving new relationships with
the Set Cover problem. Testing under a realistic setup originated by Jasin and
Sinha (2015), we find the improvement provided by our new rounding schemes to
in fact be greater than what their theoretical guarantees suggest.

This research is partially funded by a grant from Amazon.com Inc., which is
awarded through collaboration with the Columbia Center of AI Technology
(CAIT). The author thanks anonymous reviewers from several venues—MSOM SIG
2022, ACDA 2023, and EC 2023—for excellent comments that improved the
manuscript. The author also thanks Levi DeValve, Stefanus Jasin, Aravind
Srinivasan, Yehua Wei, and Linwei Xin for sharing background information about
this problem.

## References

  * Acimovic and Farias (2019) Acimovic J, Farias VF (2019) The fulfillment-optimization problem. _Operations Research & Management Science in the age of analytics_, 218–237 (INFORMS).
  * Acimovic and Graves (2015) Acimovic J, Graves SC (2015) Making better fulfillment decisions on the fly in an online retail environment. _Manufacturing & Service Operations Management_ 17(1):34–51.
  * Amil et al. (2022) Amil A, Makhdoumi A, Wei Y (2022) Multi-item order fulfillment revisited: Lp formulation and prophet inequality. _Available at SSRN 4176274_ .
  * DeValve et al. (2021) DeValve L, Wei Y, Wu D, Yuan R (2021) Understanding the value of fulfillment flexibility in an online retailing environment. _Manufacturing & Service Operations Management_ .
  * Dinur and Steurer (2014) Dinur I, Steurer D (2014) Analytical approach to parallel repetition. _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , 624–633.
  * Dunning et al. (2017) Dunning I, Huchette J, Lubin M (2017) Jump: A modeling language for mathematical optimization. _SIAM review_ 59(2):295–320.
  * Jasin and Kumar (2012) Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. _Mathematics of Operations Research_ 37(2):313–345.
  * Jasin and Sinha (2015) Jasin S, Sinha A (2015) An lp-based correlated rounding scheme for multi-item ecommerce order fulfillment. _Operations Research_ 63(6):1336–1351.
  * Lei et al. (2018) Lei Y, Jasin S, Sinha A (2018) Joint dynamic pricing and order fulfillment for e-commerce retailers. _Manufacturing & Service Operations Management_ 20(2):269–284.
  * Lei et al. (2021) Lei Y, Jasin S, Uichanco J, Vakhutinsky A (2021) Joint product framing (display, ranking, pricing) and order fulfillment under the multinomial logit model for e-commerce retailers. _Manufacturing & Service Operations Management_ .
  * Motwani and Raghavan (1995) Motwani R, Raghavan P (1995) _Randomized algorithms_ (Cambridge university press).
  * Raghavan and Tompson (1987) Raghavan P, Tompson CD (1987) Randomized rounding: a technique for provably good algorithms and algorithmic proofs. _Combinatorica_ 7(4):365–374.
  * Talluri and Van Ryzin (2004) Talluri KT, Van Ryzin G (2004) _The theory and practice of revenue management_ , volume 1 (Springer).
  * Vazirani (2001) Vazirani VV (2001) _Approximation algorithms_ , volume 1 (Springer).
  * Wang et al. (2022) Wang Y, Wang X, Deng Y, Cao L, Wang T (2022) Data-driven order fulfillment consolidation for online grocery retailing, working Paper.
  * Wei et al. (2021) Wei L, Kapuscinski R, Jasin S (2021) Shipping consolidation across two warehouses with delivery deadline and expedited options for e-commerce and omni-channel retailers. _Manufacturing & Service Operations Management_ 23(6):1634–1650.
  * Xu et al. (2009) Xu PJ, Allgor R, Graves SC (2009) Benefits of reevaluating real-time order fulfillment decisions. _Manufacturing & Service Operations Management_ 11(2):340–355.
  * Zhao et al. (2020) Zhao Y, Wang X, Xin L (2020) Multi-item online order fulfillment: A competitive analysis. _Chicago Booth Research Paper_ (20-41).