Online Metric TSP: Beyond the $\sqrt{n}$ Barrier

We note that the lower bound construction that we will give later to prove Theorem 2 is actually for the online sorting problem, which is a special case of onine metric TSP. In [6], the authors showed that using $m=O(n{\log }^{2}n)$, one can achieve a competitive ratio of $O(1)$ for the online sorting problem. However, this result does not contradict the lower bound in this paper since the previous result assumed that the algorithm knows the value of $\mathrm{𝗈𝗉𝗍}$ from the outset, while the lower bound is for the case where the value of $\mathrm{𝗈𝗉𝗍}$ is unknown to the algorithm. It remains open whether an $O(1)$-competitive algorithm exists for the online metric TSP problem for the case of known $\mathrm{𝗈𝗉𝗍}$.

Our starting point is the previous result for the online sorting problem with $m>n$ [6]. This paper gave an $O({\log }^{3}n/\epsilon )$-competitive algorithm using $m=(1+\epsilon )n$ space, based on a novel data structure called an elementary tree. The core idea is to maintain a collection of binary trees whose leaves, ordered from left to right, correspond to array cells, and which guide the insertion of arriving elements.

We briefly recall how elementary trees are used to insert elements. The algorithm dynamically and sequentially labels internal tree nodes with dyadic intervals, whose lengths correspond to the heights of the nodes. For example, if the element range is $[0,1]$, the root is labeled $[0,1]$, but its two children may both be labeled $[0,1/2]$, or $[1/2,1]$, or one of each. This continues down the tree with the interval length halving at each level. The label of a node $v$ specifies the range of element values that may occupy the array cells corresponding to the leaves of the subtree rooted at $v$. Crucially, except at the root, these labels are assigned dynamically and depend on the insertion sequence.

When a new element arrives, the algorithm performs a depth-first search to find a node whose interval label contains the element and which has an unlabeled child. That child is then labeled with the unique dyadic interval at that level containing the element, and the procedure recurses down the tree until the element is placed at a leaf. This approach fundamentally exploits the shared linear order of the line metric and the array, a property that does not extend to general metric spaces.

Extending this framework to general metrics faces several obstacles. First, unlike dyadic intervals, recursive covers (by balls of decreasing radii) of general metric spaces typically involve overlapping regions, which violates laminarity. (Note that laminarity requires that any two of the covering sets should either be disjoint or one should be contained in the other.) As a result, a point may not belong to a unique ball at a given level, introducing ambiguity that the insertion algorithm must resolve. Second, while dyadic intervals split into exactly two subintervals at each level, a ball in a general metric space may require many smaller balls to cover it at the next scale, with the number governed by the doubling dimension. Since elementary trees are binary, this creates a mismatch between the recursive structure of the metric space and the tree arity.¹¹1In fact, the doubling dimension can be arbitrarily large for a general metric space. Increasing the arity is also generally infeasible, as it would lead to excessive space usage. Finally, there is a more fundamental disconnect: while dyadic intervals inherit a natural left-to-right order from the line metric compatible with the array, there is no canonical linear ordering of balls of the same radius in a general metric space.

To overcome these difficulties, we introduce a new data structure in this paper called a metric ball-cover tree (MBC tree). Our first step is to construct a dynamic recursive cover of the metric space using balls of geometrically decreasing radii. Unlike dyadic intervals on the line that are statically defined, the balls in our cover are defined based on the arrival sequence. When a new point arrives, the algorithm identifies the highest level at which it is not already covered by an existing ball and creates balls of progressively smaller radii from that level onward, all centered at the new point.

Given this (dynamically evolving) ball-cover of the metric space, an MBC tree is a binary tree where the nodes are dynamically labeled by points in the metric space. Labeling a node $v$ at height $h$ with a point $p$ in the metric space commits the array cells corresponding to the leaves under $v$ in the MBC tree to points in a ball of radius $r$ centered at $p$, where $r$ is a fixed function of $h$.

This brings us to our main challenge: we need to define the rules of labeling an MBC tree culminating in the insertion of a new point in the array. A natural attempt would be to reuse the depth-first insertion procedure of [6], but as we show in Appendix B, this approach fails to preserve the desired guarantees in general metric spaces. Instead, we introduce a new bottom-up labeling strategy. To motivate it, consider the risk associated with labeling a node $v$ by a ball of radius $r$ centered at a newly arrived point $p$. Since labels are irrevocable, this commits the entire subtree under $v$ to points within that ball, even though only a single point has been observed so far. If no other points ever fall into this ball, the remaining array cells in that subtree are wasted.

This phenomenon is significantly more severe in general metric spaces than on the line. Suppose we call a subtree that receives only a single insertion a wasted subtree. Note that each ball/interval can only correspond to a single wasted subtree, since any subsequent insertion in the ball/interval would not label a new node at the same level. For dyadic intervals on the line, this is a strong property: it immediately implies that the total wasted space is cumulatively no more than the size of the subarray under a single elementary tree, since each dyadic interval splits into exactly two subintervals at the next level. Indeed, by constructing elementary trees with $\epsilon n$ leaves, the algorithm of [6] ensures that the total wasted space is $\epsilon n$.

In contrast, in a general metric space, a ball may split into many smaller balls at the next level. Since the tree remains binary, this can cause the total wasted space to grow well beyond the size of a single tree. Increasing the tree arity to match the doubling dimension does not resolve this issue, as it merely coalesces the wasted space to a larger subarray that now corresponds to the leaves of an elementary tree of fixed height.

To overcome this bottleneck, we adopt a frugal allocation strategy in MBC trees: we label the deepest unlabeled node that can legitimately be assigned to the new point. This bottom-up approach minimizes the amount of space committed based on limited evidence. However, abandoning the depth-first insertion procedure in [6] necessitates a fundamentally new analysis of both space usage and competitive ratio of the algorithm. We describe the MBC tree data structure and the online metric TSP algorithm in Section 2. For simplicity, we first assume that the optimal value $\mathrm{𝗈𝗉𝗍}$ is known to the algorithm. Under this assumption, we obtain an $O({\log }^{2}n/\epsilon )$-competitive algorithm using $m=(1+\epsilon )n$ space. Removing the assumption that $\mathrm{𝗈𝗉𝗍}$ is known incurs an additional $O(\log n)$ factor in the competitive ratio, following techniques similar to [6]. This extension is presented in Appendix A, completing the proof of Theorem 1.

Our lower bound construction (Theorem 2) applies to online sorting [1], the special case of online metric TSP on the line. A key feature of the construction is that the optimal value $\mathrm{𝗈𝗉𝗍}$ is not known to the online algorithm. While this assumption is standard in online metric TSP, some prior work on online sorting assumes that all elements lie in $[0,1]$ and that both endpoints appear in the instance, effectively fixing $\mathrm{𝗈𝗉𝗍}=1$. Our lower bound does not apply in this setting; indeed, when $\mathrm{𝗈𝗉𝗍}$ is known, $O(1)$-competitive algorithms with $m=O(npolylogn)$ space are known for online sorting [6].

Recall that in online sorting, elements arrive online and must be placed into an array of size $m$ so as to minimize the sum of absolute differences between consecutive non-empty cells. The lower bound proceeds in multiple phases. Suppose in the first phase, the adversary presents batches of elements that are evenly spaced within the interval $[1,2]$. The algorithm’s behavior can be summarized by the structure of the holes, i.e., the empty regions between occupied array cells. If the algorithm keeps these holes small, it is being frugal with space, but the adversary responds by increasing the batch sizes while keeping the value range fixed. Maintaining small holes under such dense arrivals forces the algorithm to incur a large competitive ratio, as it repeatedly pays cost at the boundaries between batches.

Eventually, to control its competitive ratio, the algorithm must create sufficiently large holes. At this point, the adversary switches strategy and begins presenting elements in a much larger range $[k,2k]$, for large $k$. This effectively turns the earlier elements into zeros relative to the new scale. Since the algorithm lacks sufficient unused space, it must reuse the previously created large holes. Inserting large values into these holes immediately incurs cost $\mathrm{\Theta }(k)$ at the boundaries, which matches the order of $\mathrm{𝗈𝗉𝗍}$ at this stage. If this happens in too many holes, the algorithm again suffers a large competitive ratio.

Our construction, given in full in Section 3, iterates this process over multiple rounds and refines the idea presented above to obtain the lower bound stated in Theorem 2.

The procedure starts by identifying a node $v^{\prime }$ as follows:

• $\mathrm{■}$

  If $v$ is a partial node, $v^{\prime }$ is the right child of $v$.

• $\mathrm{■}$

  Otherwise, $v$ is the root of a new tree; in this case, $v^{\prime }:=v$.

Starting from $v^{\prime }$, the algorithm traverses down to a leaf by repeatedly choosing the left child. For every node $w$ on this path (including $v^{\prime }$), we mark $w$ with center $c_w=x$ and radius $r_h$ where $h$ is the height of $w$. Finally, $x$ is stored at the leaf $u$ at the end of this path.

In Figure 2, we show the insertion of a new point in an MBC tree.

Without loss of generality, assume $u$ was marked before $v$ (created by the insertion of a point $x_v$). When the algorithm attempted to insert $x_v$, it checked all existing marked nodes at height $h$, including $u$. Since $u$ is partial, it had an available (unmarked) child, which means the insertion into $u$ would have succeeded if $x_v$ were admissible.

The fact that $x_v$ was not inserted in the subtree under $u$, while the insertion algorithm prefers the partial node at the lowest possible height, implies that $x_v$ is inadmissible at $u$. Therefore, $d(x_v,c_u)>r_h$. Since $c_v=x_v$, it follows that $d(c_v,c_u)>r_h$. $\mathrm{⊲}$

Using Claim 5, we now prove Claim 4.

Let $N_h$ be the number of partial nodes at height $h$. By Claim 5, their centers are $N_h$ points that are pairwise separated by distance $>r_h$. Since the optimal TSP tour (of cost $\mathrm{𝗈𝗉𝗍}$) visits all points, it must connect these $N_h$ centers incurring a cost $>(N_h-1)\cdot r_h$. Substituting $r_h=R\cdot 2^{h-H}=\mathrm{𝗈𝗉𝗍}\cdot 2^{h-H}$, we get $N_h\le 2^{H-h}$.

Since each partial node at height $h$ has an unmarked child node at height $h-1$ that has $2^{h-1}$ unused array cells under it, the total unused space in the array is at most

$\mathrm{⊲}$

We can now derive the space usage of the online algorithm from Claim 4.

By Claim 4, it follows that the total empty space is at most:

$◀$

There are two possibilities. The first is that $c_v=c_u$. In this case, the claim trivially holds. Otherwise, the labeling at $u$ was done by the procedure $\mathrm{𝚒𝚗𝚜𝚎𝚛𝚝}(v,c_u)$, which can only be run if $c_u$ is admissible at $v$. $\mathrm{⊲}$

We will prove the claim by induction on $h$. For the base case of $h=1$, we have from Claim 8 that $x$ is admissible at $v$. Therefore, $d(x,c_v)\le r_1$.

Let $v_0=u,v_1,\mathrm{\dots },v_{h-1},v_h=v$ denote the vertices on the path from a leaf $u$ to its ancestor $v$ at height $h$. Let $z$ denote $c_{v_{h-1}}$. By the inductive hypothesis, we have $d(x,z)\le {\sum }_{k=1}^{h-1}{r}_k$. Furthermore, using Claim 8, we know that $d(z,c_v)\le r_h$. Therefore, by the triangle inequality,

$\mathrm{⊲}$

Using the above claim, we establish a bound on the total cost within an MBC tree.

Let $x_i,x_{i+1}$ be a pair of points that occupy consecutive non-empty cells in the array (the leaves of $A$). Let $v$ denote the least common ancestor of $x_i$ and $x_{i+1}$ in $A$, and let $v_{\mathrm{\ell }},v_r$ be the left and right children of $v$.

By the structure of the tree, $x_i$ is the rightmost non-empty leaf in the subtree rooted at $v_{\mathrm{\ell }}$, and $x_{i+1}$ is the leftmost non-empty leaf in the subtree rooted at $v_r$. By Claim 9, we have $d(x_i,c_v)\le 2r_h$ and $d(c_v,x_{i+1})\le 2r_h$. Therefore, by the triangle inequality, we get

We charge this distance $d(x_i,x_{i+1})$ to the node $v$. Every internal node in the MBC tree is charged at most once. Summing over all heights $h=1\mathrm{\dots }H$, we get that the total cost is at most

$◀$

We now return to the proof of Lemma 7.

By Lemma 6, the total space used by the algorithm is at most $(1+\epsilon )n$. The size of the subarray under a single MBC tree of height $H$ is

Therefore, the number of MBC trees, denoted $k$, is at most

We now sum the costs. The total cost consists of the cost within each MBC tree and the cost incurred between MBC trees.

By Lemma 10, the cost of a single MBC tree is at most $4H\cdot \mathrm{𝗈𝗉𝗍}$. Since $H\le \log (\epsilon n)\le \log n$, the cumulative internal cost across all $k$ trees is at most:

We are left with the cost incurred between MBC trees, i.e., by the rightmost point in $A_i$ and the leftmost one in $A_{i+1}$. For any pair of points, the distance is at most $\mathrm{𝗈𝗉𝗍}$. Thus, the total cost between trees is at most

Adding these two types of cost, we get that the total cost is at most

$◀$