A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP

In a recent parallel and independent work, Hu [11] studied Stochastic Online Sorting and obtained a deterministic algorithm with expected cost at most $\log n\cdot 2^{O({\log }^{\ast }n)}$ and an elegant lower bound of $\mathrm{\Omega }(\log n)$ on the expected cost of any randomized algorithm. Regarding high-probability bounds, which we aim to derive in this work, Hu [11, Theorem 1.3] presented an $O({\log }^{20}n)$-competitive algorithm.

The first main idea that Abrahamsen et al. [2] introduced is to divide the array into buckets / bins, exploit the randomness of the input in order to assign each element to a bucket, and solve the problem separately in each bucket. Suppose that each bucket has $C$ elements; thus, we have $n/C$ buckets, and the bucket $i$ contains elements in $((i-1)\frac{C}{n},i\frac{C}{n}]$. Then, assuming that each bucket will receive exactly the expected number of elements, i.e. $C$ elements, the cost of the algorithm is approximately $\text{Alg}=\text{number of buckets}\times \text{cost inside bucket}=O(\sqrt{C})$, assuming that the $O(\sqrt{n})$ adversarial algorithm of Aamand et al. [1] was employed in each bucket.

Hence, smaller buckets reduce cost but increase the chance of imbalance, while larger buckets stabilize the load at the expense of higher internal cost. This trade-off is central to their analysis. To handle the imbalances, a part of the array in the end is reserved, also called backyard, and its size depends on how large these imbalances are. Since elements inserted in the backyard are arbitrary, the algorithm incurs a cost equal to the square root of its size. Thus, the previous trade-off translates into a trade-off between the size of the backyard and $C$: the larger $C$ is, the smaller the backyard and vice versa. Their first algorithm balances this trade-off and achieves $\tilde{O}(n^{1/3})$ complexity. Recursively using their algorithm inside the buckets, they improve their competitive ratio to $\tilde{O}(n^{1/4})$.

Our approach to Stochastic Online Sorting can be naturally described through the lens of the balls-into-bins paradigm. More specifically, the algorithm proceeds by maintaining a partitioning of a certain part of $A$ into equally sized bins, while the arriving elements can be regarded as balls placed into bins. Each bin is associated with a certain subinterval of $[0,1]$, which determines if a new ball / element is placed into the particular bin. The subintervals associated with the bins form a partitioning of $[0,1]$ and are of equal length. Hence, since the elements are i.i.d. samples from the uniform distribution on $[0,1]$, each new ball is placed uniformly at random (and independently of the other balls) in each bin.

Interpreting the $\tilde{O}(n^{1/3})$-competitive algorithm of Abrahamsen et al. [2] through the balls-into-bins framework above, we realize that the main limitation of their approach is that they consider a single balls-into-bins instance, which has very large bins and is fixed at the beginning of the algorithm. Therefore, the backyard of $A$ must be large enough, in order to accommodate the significant imbalances in the bins’ occupancy.

Our key new technical insight is that we can decompose an instance of Stochastic Online Sorting into a hierarchy of balls-into-bins instances (a.k.a. phases) of geometrically decreasing size. Crucially, we first distinguish between buckets and bins. A bucket is a contiguous set of cells corresponding to a single interval of the domain, while a bin is a collection of buckets that together cover the same interval but need not be contiguous in the array. It is important, that we select the bucket sizes dynamically, when we proceed from one phase to the next, in order to create same sized bins to deal with any imbalances (i.e., empty cells in some buckets) left from the previous phase.

Our algorithm (see also Section 2 and Algorithm 1 for the details) maintains that all bins in the same phase are of equal size (and have equal probability of receiving a new element) and all bins created by the algorithm have size $\mathrm{\Theta }({\log }^{2}n)$ (though the bucket size may slightly vary between phases). In the first phase, we consider the first $n/2$ cells of $A$, which we partition into $n/(2{\log }^{2}n)$ buckets (we also partition $[0,1]$ into the same number of subintervals with equal length). The current phase ends when the first of its buckets becomes full. A standard concentration bound (Lemma 5) shows that w.h.p. before the first phase ends: (i) at least $(1-o(1))\frac{n}{2}$ elements are successfully placed into its bins; and (ii) every bin has received at least $(1-o(1)){\log }^{2}n$ elements. Using the (adversarial) $O(\sqrt{n})$-competitive algorithm of Aamand et al. [1] to deal with the exact placement of the elements in the same bin we get that w.h.p. the total cost of the algorithm during its first phase is $O(\log n)$.

In the second phase, we consider the next $n/4$ cells of $A$ which are partitioned into $n/(4{\log }^{2}n)$ buckets (as before, we partition $[0,1]$ into the same number of subintervals with equal length). The bin size is slightly larger than in the first phase (but again at most $(1+o(1)){\log }^{2}n$), because in the bins we also include cells from buckets left empty in the first half of $A$ from the previous phase. As above, w.h.p. before the second phase ends: (i) at least $(1-o(1))\frac{n}{4}$ elements are successfully placed into its bins; (ii) every bin has received at least $(1-o(1)){\log }^{2}n$ elements; and (iii) the total cost of the algorithm for its second phase is $O(\log n)$. Moreover, we show that due to property (ii) (combined for the first and the second phase), w.h.p. before the second phase ends, all cells in the first half of $A$ (i.e., the cells considered in the first phase) are full. So, we maintain the invariant that any imbalances in bucket occupancy left from the first (resp. any) phase do not carry over to the phases after the second (resp. next one).

Using the steps and the invariants (and carefully defining the exact quantities hidden in the $o(1)$ notation) above, our algorithm proceeds from one phase to the next, for $O(\log n)$ phases, until we are left with a single bucket of size $\mathrm{\Theta }({\log }^{2}n)$. The total cost is dominated by the algorithm’s total cost for the different phases and is $O({\log }^{2}n)$ w.h.p..

When extending to higher dimensions, three challenges arise. First, unlike in the one-dimensional setting, there is no simple closed-form expression for Opt, and we must instead rely on getting a good estimate of Opt using concentration bounds. Second, the domain must be partitioned into blocks that both (i) have equal probability mass, to preserve the balls-into-bins property, and (ii) contain points that are sufficiently close so that the intra-block cost is negligible compared to Opt. Third, there is no obvious ordering of the blocks that guarantees low inter-block cost. To overcome these difficulties, we exploit properties of the uniform distribution, which allows us to partition the space into hyperboxes of similar geometry. We then define a tour that visits the input points block by block, with consecutive blocks chosen to be adjacent. The ordering of blocks is inspired by space-filling curves, a tool that has been widely used in the study of universal TSP (see [14, 7, 10, 8]). We prove that this structured tour is within a constant factor of the optimal TSP tour w.h.p., and we adapt our algorithmic framework to approximate it using Bertram’s algorithm [6]. As a result, we retain the $O({\log }^{2}n)$ guarantee in higher dimensions.

Another interesting variant of the Online Sorting Problem is one where the size of the array $m$ is longer than the input sequence, i.e., $m>n$. This version was introduced by Aamand et al. [1], who designed a deterministic $2^{\sqrt{\log n}\sqrt{\log \log n+\log (1/ϵ)}}$-competitive algorithm when $m=(1+ϵ)n$. They complemented this with a lower bound, showing that every deterministic algorithm with $m=\gamma n$ is at least $1/\gamma \cdot \mathrm{\Omega }(\log n/\log \log n)$-competitive. Later, Azar et al. [4] and Nirjhor et al. [13], in independent and concurrent work, improved the upper bound, nearly resolving this variant.

The connection between stochastic online sorting and hashing was already observed by Abrahamsen et al. [2]. Two particularly relevant examples are Filter Hashing, introduced by Fotakis et al. [9], and Transactional Multi-Writer Cuckoo Hashing, proposed by Kuszmaul [12]. Both hashing schemes employ a multi-layered structure where each subsequent layer is tasked with handling the imbalances of the previous layers.

Online TSP has also been studied in different contexts. A notable line of work interprets it as a scheduling problem: points (or requests) appear online in a metric space, and the objective is to minimize the time until all points have been visited [3]. In contrast, our setting focuses on minimizing the total length of the tour, rather than the completion time.

• $\mathrm{■}$

  $\text{DomainPartitioning}(𝒟,𝒮,\mathrm{\ell })$: This procedure takes as input a distribution $𝒟$ over a domain $𝒮$ and a positive integer $\mathrm{\ell }$. It outputs subsets $\{T_j^{(i)}\subseteq 𝒮:i\in [\mathrm{\ell }+1],j\in [2^{\mathrm{\ell }-i+1}]\},$ collectively denoted by $𝒯$. The collection $𝒯$ satisfies, for every level $i\in [\mathrm{\ell }+1]$:

  1. 1.

     Covering: ${\bigcup }_{j\in [2^{\mathrm{\ell }-i+1}]}{T}_j^{(i)}=𝒮.$

  2. 2.

     Disjointness: The sets ${\{T_j^{(i)}\}}_{j\in [2^{\mathrm{\ell }-i+1}]}$ are pairwise disjoint.

  3. 3.

     Equal Mass: ${\mathbb{P}}_{x\sim 𝒟}\left[x\in T_j^{(i)}\right]\text{ is the same for all }j\in [2^{\mathrm{\ell }-i+1}].$

  4. 4.

     Laminarity: $𝒯$ forms a laminar family – every pair of sets in $𝒯$ is either disjoint or one is contained in the other.

  Thus $𝒯$ defines a hierarchical, binary-tree partition of $𝒮$, consisting of $2^{\mathrm{\ell }+1}-1$ subsets in total.

• $\mathrm{■}$

  $\text{InBucketPlacement}(x,a)$: This function takes as input an element $x\in 𝒮$ and places it into an empty cell of sub-subarray $a$ of $A$.

• $\mathrm{■}$

  $\text{index}(𝒯,i,x)$: This function takes as input a set $𝒯$ outputted by DomainPartitioning, a positive integer $i$ and an input element $x$ and outputs the unique index $k$ such that $x\in T_k^{(i)}$.

• $\mathrm{■}$

  empty($a$): This function takes as input a (sub-)subarray $a$ of $A$ and returns the number of empty cells in $a$ at the current point of execution.

We also introduce the following definition:

The complete pseudocode is given in the Appendix of the full version; a more high-level version is presented in Algorithm 1. We now describe the algorithm step by step.

First, we define $\mathrm{\ell }$ as the unique positive integer such that . The initial number of buckets for the first subarray and balls-into-bins instance is $K=2^{\mathrm{\ell }}$. Next, we partition the domain $𝒮$ using the subroutine DomainPartitioning, which provides the partitioning of the domain into subsets (intervals / blocks) based on which we determine the bucket each element $x\in 𝒮$ is inserted to. After completing the initializations, we move on to the first phase of the algorithm.

Let $A_1$ be the subarray containing the first $\lfloor \frac{n}{2}\rfloor$ elements of the original array. In the first phase we will place elements inside this subarray using a hash-based logic. We divide the $A_1$ elements into $K_1=2^{\mathrm{\ell }}$ contiguous buckets, of size $C_1=\frac{A_1}{K_1}=\mathrm{\Theta }({\log }^{2}n)$ elements each. We place an arriving element $x\sim 𝒟$ in the $k$-th bucket of $A_1$ if and only if $x\in T_k^{(1)}$, and then use the subroutine InBucketPlacement to position it within the bucket.

By definition of $𝒯$, each sample has equal probability of being placed into each bucket. Hence, placement of elements into the buckets of $A_1$ at the first phase of our algorithm can be thought as a balls-into-bins instance where we throw balls into $K_1$ bins, uniformly at random. When an element arrives and its designated bucket is full, we say that an overflow has occurred, triggering a transition to phase $2$.

In order to handle overflows from subarray $A_1$ we allocate a subarray $A_2$ of size $\lfloor \frac{n}{4}\rfloor$ next to $A_1$. Subarray $A_2$ is divided into $K_2=K_1/2=2^{\mathrm{\ell }-1}$ buckets. Regarding bucket sizes, crucially, the size of each bucket of $A_2$ is not the same, as discussed in the technical overview. To gain some intuition for the bucket sizes set in Line 8, we consider the following example.

Suppose for simplicity’s sake, that we are on the classic online sorting case and subarray $A_1$ has $100$ cells and is divided into $K=K_1=4$ buckets, with capacity $C_1=25$ each, such that $T_1^{(1)}=(0,0.25),T_2^{(1)}=(0.25,0.5),T_3^{(1)}=(0.5,0.75),T_4^{(1)}=(0.75,1)$ respectively. Assume that bucket $a_1^{(1)}$ is overflowed and the number of elements in each bucket are $(25,20,10,15)$ at the time exactly before the overflow. Then, the up to this point empty, subarray $A_2$ will be brought into action to take care of the overflows of subarray $A_1$. By design, $A_2$ has $50$ cells and $K_2=K_1/2=2$ buckets that handle elements $T_1^{(2)}=(0,0.5),T_2^{(2)}=(0.5,1)$ respectively. If we allocate $25$ cells to each bucket in $A_2$, then we expect the first one to overflow significantly faster than the second one since in $A_1$ there are less empty cells for elements lying in $(0,0.5)$ than for elements lying in $(0.5,1)$. Thus, in order to handle the imbalances in $A_1$ we will allocate more cells in the first bucket in $A_2$. The total number of empty cells in $A_1$ is $\text{empty}(A_1)=0+5+15+10=30$ and since we add $50$ cells with $A_2$ we have in total $80$ cells – this is the size of the second balls-into-bins instance. Specifically, we can consider that the instance has $2$ bins that handle elements from $(0,0.5)$ and $(0.5,1)$ respectively. The first bin contains the first two buckets of $A_1$ and the first bucket of $A_2$. The second bin contains the last two buckets of $A_1$ and the second bucket of $A_2$. We would like the capacities of the bins to be close enough in order to have a balanced balls-into-bins instance, thus equal to $\frac{\text{empty}(A_1)+A_2}{K_2}=40$. Thus, we allocate $c_1^{(2)}=40-\text{empty}(a_1^{(1)})-\text{empty}(a_2^{(1)})=35$ cells for the first bucket in $A_2$ and $c_2^{(2)}=40-\text{empty}(a_3^{(1)})-\text{empty}(a_4^{(1)})=15$ cells for the second one. As a result, we obtain a new balanced balls-into-bins instance: the bins have equal capacity, so the expected overflow occurs later than it would if $A_2$ were simply divided into two equal-sized buckets.

This illustrates how $A_2$’s bucket sizes compensate for imbalances in $A_1$. We now return to the formal description of phase 2. The capacity of each bin in the second balls-into-bins instance is thus:

(see also Lemma 4) and each bucket has capacity as defined in Line 8 in order to create a balanced instance, i.e. $c_j^{(2)}=C_2-\text{empty}\left(a_{2j-1}^{(1)}\right)-\text{empty}\left(a_{2j}^{(1)}\right)$. If we cannot allocate such bucket size we say that our algorithm failed.

Regarding element placement, each bucket $j$ in $A_2$ accepts elements from the subset $T_j^{(2)}$. As elements arrive online, we first attempt to place them in their designated bucket in $A_1$; if it is full, we place them in the corresponding bucket in $A_2$. When an element arrives and its designated bucket in $A_1$ and $A_2$ is full, we transition to phase $3$ and we say that a bucket in array $A_2$ overflowed. Crucially, if $A_1$ is not full at this point, we say that the algorithm has failed. In Section 2.2, we show that our algorithm does not fail with high probability.

The same logic extends to all subsequent phases, while the main invariant remains: each subarray fills before a bucket of the next subarray overflows, otherwise our algorithm fails. When the remaining places in the array are less than $100{\log }^{2}n$ we transition to the last phase of our algorithm. Note that for $C_i$ in each phase it holds (its proof is in the Appendix of the full version):

In the final phase, the last subarray, denoted by $B$, is a single bucket, and elements are inserted using InBucketPlacement. Due to the above-discussed invariant, when $B$ overflows (i.e., when it is completely filled, as it has only one bucket), all previous subarrays are full. Thus, we have placed all elements into the array and the algorithm returns success.

Let $R$ be the number of phases of our algorithm and let $B$ be the last subarray $A_R$. For $R$ it holds that $B+{\sum }_{i=1}^{R-1}\lfloor \frac{n}{2^i}\rfloor =n$ with $B\le 100{\log }^{2}n$. Hence,

and since $n-{\sum }_{i=1}^{R-2}\lfloor \frac{n}{2^i}\rfloor >100{\log }^{2}n$ we get that $R\le 1+\log \left(\frac{n}{100{\log }^{2}n}\right)$, thus $R=\mathrm{\Theta }(\log \frac{n}{{\log }^{2}n})$. Also, the size of $A_{R-1}$ is $n/2^{R-1}=\mathrm{\Theta }({\log }^{2}n)$ and for $B$ it holds that $B\ge n-n(1-2^{-R})=\mathrm{\Theta }({\log }^{2}n)$, thus $B$ and $A_{R-1}$ are asymptotically tight, preserving the invariant.

We proceed using strong induction (see also Figure 1 for a visual representation of the proof).

We aim to show that the first subarray $A_1$ is filled before any overflow occurs in the second balls-into-bins instance, that is, $T_2\ge T_1^{\prime }-T_1$, conditioned on $ℰ$. For the first phase, it holds $T_1=A_1-N_1$ (there is no previous phase). Thus, the size of the second balls-into-bins instance is $A_2+N_1$. Now, using Definition 6, observe that:

since $A_2>A_1/4$, thus conditioned on $ℰ$ we obtain the desired result, proving the base case.

Assume the statement holds for each $i\in [r-1]$. We aim to prove that it also holds for $i=r$. From induction hypothesis, since we condition on $ℰ$, every subarray $A_j$ for $j\in [r-1]$ becomes completely filled before any bucket in $A_{j+1}$ overflows. As a result, when phase $r+1$ starts, every subarray $A_j$ for $j\in [r-1]$ is filled. This is crucial, since it implies that every new sample that arrives is inserted in this balls-into-bins instance; thus we can use Definition 6 (otherwise the elements inserted into the instance are not necessarily uniform in bins). The size of the balls-into-bins instance of phase $r+1$ is $A_{r+1}+N_r$. Now, using Definition 6 again, observe that:

where we have used that $A_i=\mathrm{\Theta }(A_{i-1})$, completing the proof of the induction step and thus proving the lemma. $◀$

We establish the following lemma, whose proof is deferred to the Appendix of the full version.

Since $ℰ$ implies that our algorithm will not fail we get that our algorithm does not fail with high probability since:

We refer to the blocks $T^{(1)}=\{b_1,b_2,\mathrm{\dots },b_{2^{\mathrm{\ell }}}\}$ at the lowest level of our hierarchy as elementary blocks. Within an elementary block, all points are treated identically by Algorithm 1: by construction, the algorithm’s decisions do not depend on which specific point from the block is presented. Consequently, we may assume that the points drawn within an elementary block $b$ are i.i.d. samples from the uniform distribution $𝒰(b)$²²2Note that $𝒰(b)$ is the restriction of the global distribution $𝒟$ to block $b$..

At this stage, we impose an order on the blocks. Consecutive blocks are assigned to consecutive buckets/sub-subarrays. In addition, they are constructed so that they merge early during the execution of our algorithm. This motivates a further property: consecutive blocks must be neighbours, i.e., they share a face (or, more generally, a hyperface). We present Algorithm 3, which traverses the blocks in such an order, and establish its correctness in Lemma 14 which is formally proven in the Appendix of the full version.

In contrast to the one-dimensional case, there is no simple closed-form expression for the optimal cost in higher dimensions. We therefore rely on asymptotic estimates and concentration bounds to control the value of Opt.

We now proceed to the analysis of the three sources of cost.

Since the domain is split $\mathrm{\ell }$ times, each dimension is split at least $\lfloor \mathrm{\ell }/d\rfloor$ times³³3We assume that $\mathrm{\ell }\ge d$. In the full version we remove this assumption., thus the maximum side length of a block is at most ${(1/2)}^{\lfloor \mathrm{\ell }/d\rfloor }$. As $\mathrm{\ell }$ and $d$ are integers, Hence, each side of $b_i$ has length at most $4{(\frac{{\log }^{2}n}{n})}^{1/d}$.

The expected length of the optimal subtour inside $b_i$ satisfies:

where $\mathrm{\Delta }$ is the side length of $b_i$. Substituting $\mathrm{\Delta }\le 4{(\frac{{\log }^{2}n}{n})}^{1/d}$ gives:

Applying Lemma 18 with $t=48{\beta }_d{n}^{-1/d}{\log }^{2}n$, we bound the probability that ${\text{Opt}}_i$ exceeds three times its expectation:

$◀$

So far, we proved that the length of the optimal tour of $6{\log }^{2}n$ points uniformly chosen in a block is bounded by $72{\beta }_d{n}^{-1/d}{\log }^{2}n$ with probability at least $1-2/n^2$. We want to transition from this to a bound of the optimal total intra bucket cost of a subarray $j$, denoted by $\text{InBucket}(j)$. For the first subarray, elementary blocks are mapped one to one to buckets and every bucket contains strictly less than $6{\log }^{2}n$ points therefore Corollary 21 implies that $\text{InBucket}(1)\le 72{\beta }_d{n}^{1-1/d}$ with probability at least $1-\frac{1}{n{\log }^{2}n}$. We now show that any subsequent (fixed) subarray enjoys a comparable bound.

A feasible tour inside $r(B_k^{(j)})$ is obtained by concatenating the optimal tours of $r(b_{k_1}),\mathrm{\dots },r(b_{k_m})$ and adding at most $(r-1)$ connecting edges between adjacent elementary blocks. Summed over all phase $j$ blocks, the total number of such connectors is at most the number of elementary blocks. By Lemma 28, each connector has length at most $2{\beta }_d{n}^{-1/d}{\log }^{2}n$, and by Corollary 30 the total intra-subarray connection cost is deterministically bounded by ${\beta }_d{n}^{1-1/d}$. This yields the claimed inequality. $◀$

At this point we restate Lemma 4 slightly changing the phrasing to fit current context.

The cardinality of $r(b_i)$ is a random variable. However, by Corollary 24, $r(b_i)$ contains fewer than $6{\log }^2(n)$ points. In both cases, the points are independently drawn uniformly at random within the same block. The proof then follows from the observation that the probability of the optimal tour length of $x$ i.i.d. points in some space $S$ exceeding a threshold $t$ is non-decreasing in the number of points $x$. $◀$

Lemma 25 combined with Lemma 20 implies $\mathbb{P}\left[\text{Opt}(r(b_i))\ge 72{\beta }_d{n}^{-1/d}{\log }^{2}n\right]\le \frac{2}{n^2}$. Taking a union bound over different elementary blocks and adding the connecting term completes the proof. $◀$

Connecting subarrays requires adding a single edge between two points, one from each subarray. Since the optimal tour Opt already spans all points in the domain, the additional cost of this connection is trivially bounded above by Opt. $◀$

We are now ready to prove Theorem 2. We decompose the total cost into four components:

• $\mathrm{■}$

  Intra-bucket: For each subarray $A_j$, placements inside buckets are handled by Bertram’s algorithm [6]. This incurs cost ${\sum }_{i=1}^{K_j}\sqrt{C_j}\cdot \text{Opt}(r(B_i))\le \mathrm{\Theta }(\log n){\sum }_{i=1}^{2^{\mathrm{\ell }}}{\text{Opt}}_i=\mathrm{\Theta }(\log n)\text{Opt}$. where the first inequality is derived from Lemma 22 and the second from Lemma 20. Since there are $R=O(\log n)$ subarrays, the total bucket cost is $O({\log }^{2}n)\text{Opt}$.

• $\mathrm{■}$

  Inter-bucket: By Lemmas 28 and 30, the additional cost of connecting all buckets within a subarray $A_i$ is at most $O(\text{Opt})$. Summing over all $k=O(\log n)$ subarrays yields a total of $O(\log n)\text{Opt}$.

• $\mathrm{■}$

  Between subarrays: Connecting consecutive subarrays requires at most one additional edge per transition. By Lemma 31, this incurs cost at most Opt per transition. With $k=O(\log n)$ subarrays, the total cost is $O(\log n)\text{Opt}$.

• $\mathrm{■}$

  Subarray $B$: The remaining elements are placed in $B$ using Bertram’s algorithm [6], incurring total cost $O(\log n)\text{Opt}$, since $|B|=O({\log }^{2}n)$.

Conditioning on the high-probability event that Corollary 21 holds for all subarrays $A_i$ and conditioning on the event that the algorithm does not fail, the total cost of the algorithm is $O({\log }^{2}n)\text{Opt}$. This completes the proof of Theorem 2.