Simple and Order-optimal Correlated Rounding Schemes for Multi-item E-commerce Order Fulfillment

A fundamental problem faced in e-commerce is -- how can we satisfy a multi-item order using a small number of fulfillment centers (FC's), while also respecting long-term constraints on how frequently each item should be drawing inventory from each FC? In a seminal paper, Jasin and Sinha (2015) identify and formalize this as a correlated rounding problem, and propose a scheme for \textit{randomly} assigning an FC to each item according to the frequency constraints, so that the assignments are \textit{positively correlated} and not many FC's end up used. Their scheme pays at most $\approx q/4$ times the optimal cost on a $q$-item order. In this paper we provide to our knowledge the first substantial improvement of their scheme, which pays only $1+\ln(q)$ times the optimal cost. We provide another scheme that pays at most $d$ times the optimal cost, when each item is stored in at most $d$ FC's. Our schemes are fast and based on an intuitive new idea -- items wait for FC's to "open" at random times, but observe them on "dilated" time scales. We also provide matching lower bounds of $\Omega(\log q)$ and $d$ respectively for our schemes, by showing that the correlated rounding problem is a non-trivial generalization of Set Cover. Finally, we provide a new LP that solves the correlated rounding problem exactly in time exponential in the number of FC's (but not in $q$).