Optimal (Randomized) Compact Routing Schemes

Optimal (Randomized) Compact Routing Schemes Shiri Chechik∗

Avi Kadria†

Gur Lifshitz‡

Liam Roditty§

arXiv:2611.04744v1 [cs.DS] 3 Nov 2026

Abstract Compact routing schemes route messages along short paths while every vertex stores little information. We study the trade-off between the stretch and the storage of compact routing schemes in undirected graphs, in four models: labeled and name-independent schemes, with average or worst-case local storage. We improve the best known stretch in all four models. We present here selected results. e 1/k ) average local Our main result is a labeled routing scheme with expected stretch 2k − 1 and O(n storage, in which only the routing is randomized. Under the Erdős girth conjecture, no scheme with this storage has stretch below 2k − 1, so our scheme is optimal, up to polylogarithmic factors in the storage. With deterministic routing, we obtain stretch ≈ 2.47k, the best known stretch for deterministic routing with average storage. Worst-case local storage is the classical setting of compact routing. The leading coefficient 4 in the stretch 4k − 5 of Thorup and Zwick [SPAA’01] was improved only by Chechik [PODC’13],
to ≈ 3.68 in unweighted graphs. In unweighted graphs, we obtain expected stretch 83 k + O(1), O(k) , and deterministic stretch ≈ 3.05k. Name-independent routing is harder, since the labels cannot be chosen, and the source knows only e 1/k ) local storage in unweighted graphs the name of the destination. The best known stretch with O(n was 96k, by Abraham, Gavoille, and Malkhi [DISC’04]. We improve it by more than a factor of 8. With average storage, we obtain expected stretch 4k − 5, which matches the labeled scheme of Thorup and Zwick. With worst-case storage in unweighted graphs, we obtain expected stretch (8k + O(1), O(k)). All our schemes for unweighted graphs extend to weighted graphs, with a small loss in the stretch in some models, and still improve the previous best unweighted bounds. ∗ Department of Computer Science, Tel Aviv University, Israel. E-mail shiri.chechik@gmail.com.

† Department of Computer Science, Bar-Ilan University, Ramat Gan 5290002, Israel. E-mail avi.kadria3@gmail.com. ‡ Department of Computer Science, Tel Aviv University, Israel. E-mail gur.lifshitz@gmail.com.

§ Department of Computer Science, Bar-Ilan University, Ramat Gan 5290002, Israel. E-mail liam.roditty@biu.ac.il. Supported in part by BSF grants 2016365 and 2020356.

1

1

Introduction

Routing is a fundamental task in computer networks, studied since the 1970s [KK77]. A routing scheme delivers messages from a source vertex to a destination vertex, where every vertex forwards a message using only the information that it stores. We study routing schemes in undirected graphs with n vertices. A routing scheme has two phases. In the preprocessing phase, the whole graph is known, and every vertex receives a routing table and a short label. In the routing phase, the source is given a message and the label of the destination, and attaches a short header to the message. Every vertex that holds the message forwards it to one of its neighbors, using only its own routing table, the label of the destination, and the header, which it may update. This repeats until the message reaches the destination. In a labeled routing scheme, the preprocessing phase chooses the labels. In a name-independent routing scheme, the labels are the original names of the vertices, so they are fixed in advance and cannot be changed in the preprocessing phase. Routing along shortest paths is possible by storing a full routing table at every vertex, but this takes Θ(n) words per vertex, which cannot be avoided.1 Compact routing schemes therefore use less storage, and ˆ v) be the length of the walk that a message route along paths that are longer than shortest paths. Let d(u, traverses from u to v. For randomized routing, it is a random variable. A scheme has (α, β)-stretch if ˆ v) ≤ α d(u, v) + β for every u, v ∈ V , where d(u, v) is the distance between u and v. For randomized d(u, ˆ v)] ≤ α d(u, v) + β for every u, v ∈ V , with expectation routing, a scheme has (α, β)-expected stretch if E[d(u, over the choice of the route. When β = 0, we write α-stretch and α-expected stretch, and call α the (expected) stretch of the scheme. The local storage of a vertex is the number of words in its routing table. We bound either the local storage of every vertex (worst-case storage) or the total storage divided by n (average storage). Our average-storage schemes work in weighted graphs. Our worst-case schemes are for unweighted graphs, and we extend them to weighted graphs in Section F. The design of compact routing schemes in undirected graphs has been studied extensively over the past several decades [PU89, ABLP90, AP92, Cow01, EGP03, TZ01, AGM04, AGM06a, AGM+ 08, AG11, Che13a, RT15, KR25a]. See Tables 1 and 2 for a summary of the previous relevant results. Under the Erdős girth conjecture,2 every routing scheme with stretch below 2k + 1 uses Ω(n1+1/k ) bits of total storage on some graph [TZ01, Zin22]. Applying this with k − 1 in place of k, stretch 2k − 1 is optimal e 1/k ) average local storage, also for expected stretch (Lemma 6).3 for O(n In this paper, we study four models of compact routing, defined by the choice between labeled and nameindependent routing and between average and worst-case local storage. In all of them, we consider an integer e 1/k ) local storage, and we compare schemes by their stretch, mainly by the leading coefficient k ≥ 2 and O(n of k. In all four models, we improve the best known stretch. Our techniques. Our results follow from new routing techniques: randomized routing, optimizing over all routing choices at once, and a cheaper search in trees for worst-case storage. In randomized routing, the routing tables and the labels are fixed in preprocessing, and only the source flips coins, to choose the route of the message. We bound the expected stretch for every source and destination. These techniques also apply in the harder name-independent model, and Section 3 describes them in more detail. We now present our results in the four models.

1.1

Labeled routing with average storage

e 1/k ) average local storage, Our main result is a labeled routing scheme with expected stretch 2k − 1 and O(n which is optimal up to polylogarithmic factors in the storage, and improves upon the previous ≈ 2.64kstretch, by Kadria and Roditty [KR25a]. 1 Every routing scheme whose routes are shorter than three times the distance uses Ω(n) bits at some vertex on some graph [GG01, Zin22]. 2 The Erdős girth conjecture [Erd64] states that, for every k ≥ 1, there are graphs with Ω(n1+1/k ) edges and girth at least 2k + 2. 3 O(·) e hides polylogarithmic factors in n, and a word has O(log n) bits.

2

Stretch O(k) 2k − 1 ≈ 2.64k, k ≥ 3 ≈ 2.47k − 1.47 2k − 1 O(k2 ) 4k − 5 4k − 7 + ε ≈ 3.68k ≈ 3.05k + 1 ( 38 k + 6, 49 k) ≈ (2.67k + 6, 0.44k) ≈ (1 + ε)3.42k + O(1) ≈ (1 + ε)3.07k + O(1)

Storage e 1/k ) average O(n e 1/k ) average O(n e 1/k ) average O(n e 1/k ) average O(n e 1/k ) average O(n e O(n1/k log ∆) worst-case e 1/k ) worst-case O(n e −1 n1/k log ∆) worst-case O(ε e 1/k ) worst-case O(n e 1/k ) worst-case O(n e O(n1/k ) worst-case e −1 n1/k log ∆) worst-case O(ε e −1 n1/k log ∆) worst-case O(ε

Graphs unweighted weighted weighted weighted weighted weighted weighted weighted unweighted unweighted unweighted weighted weighted

Reference [PU89] [ABLP90] [KR25a] Theorem 2 Theorem 1⋆ [AP92] [TZ01] [RT15] [Che13a] Theorem 4 Theorem 3⋆ Theorem 9 Theorem 10⋆

Table 1: Labeled routing schemes, where ∆ is the aspect ratio of the graph and 0 < ε < 1. A pair (α, β) ˆ v) ≤ α d(u, v) + β, or E[d(u, ˆ v)] ≤ α d(u, v) + β for rows marked ⋆ . Under denotes (α, β)-stretch, that is, d(u, 1/k e the Erdős girth conjecture, no scheme with O(n ) average local storage has stretch below 2k −1. ⋆ Expected stretch. Theorem 1. For every integer k ≥ 2, there is a (2k − 1)-expected stretch labeled compact routing scheme e 1/k ) words, labels of O(k) e e that uses average local storage of O(n words, and headers of O(1) words. Our second result is a deterministic scheme with stretch ≈ 2.47k. It improves the ≈ 2.64k of Kadria and Roditty [KR25a].
k−1 Theorem 2. For every integer k ≥ 2, there is a 1 + ln(3/2) ≈ 2.47k − 1.47 -stretch labeled compact routing e 1/k ) words, labels of O(k) e scheme with deterministic routing that uses average local storage of O(n words, and e headers of O(1) words.

1.2

Labeled routing with worst-case storage

e 1/k ) local storage at every vertex. Chechik [Che13a] Thorup and Zwick [TZ01] obtained stretch 4k−5 with O(n e 1/k ) worst-case local obtained the first leading coefficient below 4, with stretch approximately 3.68k and O(n storage in unweighted graphs. For weighted graphs, she states stretch (4 − α)k − β, for absolute constants e 1/k log D) local storage, where D is the normalized diameter, and sketches the changes α, β > 0, with O(n to her analysis for unweighted graphs. Subsequently, Roditty and Tov [RT15] obtained stretch 4k − 7 + ε, which improves the bounds for small values of k, for example to stretch 5 + ε for k = 3. We present the first improvement over the ≈ 3.68k of Chechik [Che13a]. With randomized routing, our leading coefficient is 38 ≈ 2.67, the first below 3, at the cost of an additive 94 k. Our randomized scheme has ( 83 k + 6, 49 k)-expected stretch. Theorem 3. For every integer k ≥ 2, there is a ( 83 k + 6, 94 k)-expected stretch labeled compact routing scheme e 1/k ) words, labels of O(k) e for unweighted graphs that uses worst-case local storage of O(n words, and headers e of O(1) words. Without randomization, we obtain stretch ≈ 3.05k, which also improves the ≈ 3.68k of Chechik [Che13a]. Theorem 4. For every integer k ≥ 2, there is a

8k 1+4 ln(3/2) + 1 ≈ 3.05k + 1 -stretch labeled compact routing e 1/k

scheme for unweighted graphs with deterministic routing that uses worst-case local storage of O(n e e labels of O(k) words, and headers of O(1) words. 3

) words,

1.3

Name-independent routing with average storage

Name-independent routing has been studied extensively [ABLP90,AP92,ACL+ 06,AGM+ 08,AGM04,AM05, AGM06b, AGM06a, AGGM06, KRX06, KRX16, Lai07, LR07, GGHI13], and yet the best known stretch with e 1/k ) local storage at every vertex in unweighted graphs is 96k [AGM04], far from the lower bound of O(n 2k − 1 [AGM06a]. We present new name-independent schemes, randomized and deterministic, with average and with worste 1/k ) case local storage. Theorems 5 to 8 below improve the previous 96k by a factor of more than 8. With O(n average local storage, we obtain expected stretch 4k − 5 with randomized routing, and stretch ≈ 5.77k with deterministic routing. Theorem 5. For every integer k ≥ 2, there is a (4k − 5)-expected stretch name-independent compact routing e 1/k ) words and headers of O(1) e scheme that uses average local storage of O(n words.
4 ≈ 5.77k − 4.77 -stretch name-independent Theorem 6. For every integer k ≥ 2, there is a 1 + 21/(k−1) −1 e 1/k ) words and compact routing scheme with deterministic routing that uses average local storage of O(n e headers of O(1) words. The expected stretch 4k − 5 matches the stretch of the labeled scheme of Thorup and Zwick [TZ01]. This is the best bound that an analysis based only on the distances from the source to the hierarchy of Thorup and Zwick can give, even if the source knows d(u, v) (Section 6.1).

1.4

Name-independent routing with worst-case storage

e 1/k ) local storage at every vertex in unweighted graphs, we obtain (8k + 2e − 7, 2k − 2)-expected With O(n stretch with randomized routing, where 8k + 2e − 7 ≈ 8k − 1.56, and stretch ≈ 11.54k with deterministic routing. Theorem 7. For every integer k ≥ 2, there is a (8k + 2e − 7, 2k − 2)-expected stretch name-independent e 1/k ) words and headers compact routing scheme for unweighted graphs that uses worst-case local storage of O(n e of O(1) words.
Theorem 8. For every integer k ≥ 2, there is a 8(k−1) ln 2 + 9 ≈ 11.54k − 2.54 -stretch name-independent compact routing scheme for unweighted graphs with deterministic routing that uses worst-case local storage e 1/k ) words and headers of O(1) e of O(n words. Table 2 compares our name-independent schemes with the previous ones.

1.5

Related work

Further work on compact routing studies sparse partitions and neighborhood covers [ABLP89,AP90,ABCP98], sparse graphs [AGH11, AGH12], near-linear total storage [RT16], and vertex priorities [EFN18]. Average stretch over vertex pairs [EGP07] and small stretch for most pairs in networks of low doubling dimension [KRXY07] differ from our expected stretch guarantees for each pair. Routing has also been studied for trees [FG01], planar and bounded-genus graphs [GH99, Lu10, Tho04], graphs excluding a fixed minor [AGM05], chordal graphs and related classes [DG02, DL07], doubling and Euclidean metrics [AM04, Tal04, Sli07, CGMZ16], and geometric and unit disk graphs [HP01, MW20]. Other graph families include interconnection networks [NO99, CI03] and random and Internet-like graphs [IO02, IO03, KFY04, TYZ09]. Other settings include implicit and interval routing [SK85, vLT87, Gav00], directed roundtrip routing [CW04,RTZ08], roundtrip spanners [ZL17,ZL18,PRS+ 18,CDG20,ZHL21,SZ23,HJWX24], fault-tolerant routing [CLPR12,Che13b,DP26], and distributed construction [LP13,DSDP15,EN18b,EN18a,LPP19]. Further lower bounds concern routing memory [GP96] and routing in trees [FG02]. 4

Stretch ≈ 5.77k − 4.77 4k − 5 O(k2 9k ) O(k2 2k ) O(k2 ) 96k ≈ 11.54k − 2.54 (8k + 2e − 7, 2k − 2) 25.6(1 + ε)2 k + O(1) ≈ 14.62(1 + ε)2 k + O(1)

Storage e 1/k ) average O(n e 1/k ) average O(n e 1/k ) worst-case O(n e 1/k ) worst-case O(n e 1/k log ∆) worst-case O(n e O(n1/k log ∆) worst-case e 1/k ) worst-case O(n e 1/k ) worst-case O(n e −1 n1/k log ∆) worst-case O(ε e −1 n1/k log ∆) worst-case O(ε

Graphs weighted weighted weighted weighted weighted weighted unweighted unweighted weighted weighted

Reference Theorem 6 Theorem 5⋆ [ABLP90] [ACL+ 06] [AP92] [AGM04] Theorem 8 Theorem 7⋆ Theorem 11 Theorem 12⋆

Table 2: Name-independent routing schemes, where ∆ is the aspect ratio of the graph and 0 < ε < 1. A pair ˆ v) ≤ α d(u, v) + β, or E[d(u, ˆ v)] ≤ α d(u, v) + β for rows marked (α, β) denotes (α, β)-stretch, that is, d(u, ⋆ . Schemes with worst-case storage also bound the average storage. Under the Erdős girth conjecture, no e 1/k ) local storage has stretch below 2k − 1 [AGM06a]. ⋆ Expected stretch. scheme with O(n Related distance structures include approximate distance oracles [TZ05], path-reporting oracles [EP16, ENW16, ES26, CZ24, NS24], distance labeling schemes [Pel00b, GKK+ 01, GPPR04], and spanners [ADD+ 93, BS07, RTZ05]. Distance oracles also admit trade-offs for sparse graphs [PRT12, PR14, RT23, KR25b], with lower bounds depending on query time [SVY09] or the pivot-based model [KR26b]. Further work concerns query time [MN07, Wul13, Che14, Che15] and construction time [Wul12, KR26a]. Other uses of randomization include congestion minimization [VB81, Räc02], probabilistic tree embeddings [AKPW95, Bar96, FRT04], randomized search [KRT96], and online bidding [CKNY08]. For broader background on routing and distance structures, see [Pel00a, Gav01, GP03, Elk08, Som14, Rod16].

1.6

Organization

Section 2 gives the preliminaries, including the lower bound for randomized routing (Lemma 6), and Section 3 gives an overview of our techniques. Section 4 presents our labeled schemes with average local storage, and Section 5 presents our labeled schemes with worst-case local storage. Sections 6 and 7 present our nameindependent schemes with average and with worst-case local storage. Section 8 discusses open problems. The appendices prove the optimization bounds (Sections B to E) and extend our worst-case schemes to weighted graphs (Section F). Section A summarizes all our results.

2

Preliminaries

Let G = (V, E, ℓ) be a connected undirected graph with n vertices and positive edge weights ℓ : E → R+ , where every vertex x has a unique identifier id(x) ∈ {1, . . . , n}. Let d(u, v) be the distance between u and v, and let P (u, v) be a shortest path between them.4 For X ⊆ V , let d(u, X) = minx∈X d(u, x), where d(u, ∅) = ∞, and let p(u, X) be the vertex of X closest to u. We write [k] = {0, . . . , k − 1}. Throughout the paper, all sizes are in words of O(log n) bits.5 We write RT(u) for the routing table of a vertex u and L(u) for its label. The routing table of u contains L(u). A vertex that holds a message forwards it based on its routing table, the label of the destination, and a header that it may modify. The ports 1, . . . , deg(x) of every vertex x are fixed in advance (the fixed-port model). 4 We choose the shortest paths consistently, so that they are closed under reversal and under taking subpaths, e.g., by an infinitesimal perturbation of the weights. Distances are with respect to the original weights. 5 For the word bounds, the weights are polynomially bounded integers, possibly after rescaling, so every distance fits in O(1) words.

5

2.1

Bunches and clusters

Following Thorup and Zwick [TZ05], for X, Y ⊆ V , the bunch of u is B(u, X, Y ) = {v ∈ X | d(u, v) < d(u, Y )}, and the cluster of w is C(w, Y ) = {v ∈ V | d(w, v) < d(v, Y )}. For an integer k ≥ 2, let V = A0 ⊇ A1 ⊇ · · · ⊇ Ak−1 ⊇ Ak = ∅, and let hi (u) = d(u, Ai ) be the height of u at level i. The pivots of u are defined by pk−1 (u) = p(u, Ak−1 ) and, for i < k − 1, pi (u) = pi+1 (u) if hi (u) = hi+1 (u) and pi (u) = p(u, S Ai ) otherwise. Thus d(u, pi (u)) = hi (u). The i-th bunch of u is Bi (u) = B(u, Ai , Ai+1 ), and B(u) = i∈[k] Bi (u). For w ∈ V and i ∈ [k], let Ci (w) = C(w, Ai+1 ). For w ∈ Ai \ Ai+1 , we write C(w) = Ci (w). For every u, w ∈ V , w ∈ B(u) if and only if u ∈ C(w). We use the deterministic construction of Roditty, Thorup, and Zwick [RTZ05]. Lemma 1 (Lemma 1 of [KR25a]). For every integer k ≥ 2, we can deterministically compute sets V = A0 ⊇ e 1−i/k ) and |Bi (u)| = O(n e 1/k ), for every i ∈ [k] and u ∈ V . · · · ⊇ Ak−1 ⊇ Ak = ∅ with |Ai | = O(n P e 1/k ), and double counting gives P e 1+1/k ). Our Hence |B(u)| = O(n w∈V |C(w)| = u∈V |B(u)| = O(n average-storage schemes use Lemma 1. A single cluster may be large, so our worst-case schemes use the following hierarchy, in which every cluster is small. Lemma 2 (Theorem 3.1 of [TZ01], see also Theorem A.2 of [Che13a]). For every integer k ≥ 2, we can e 1−i/k ) and |Bi (u)| = O(n e 1/k ), such that compute sets V = A0 ⊇ · · · ⊇ Ak−1 ⊇ Ak = ∅ with |Ai | = O(n (i+1)/k |C(w)| ≤ 4n for every i ∈ [k] and w ∈ Ai \ Ai+1 . Our routing schemes send the message from the source to one of its own pivots. This is possible since every vertex is in the cluster of each of its pivots. Lemma 3 (Lemma 4.1 of [TZ05]). For every u ∈ V and i ∈ [k], pi (u) ∈ B(u) and u ∈ C(pi (u)). Thorup and Zwick [TZ05] showed S that a cluster is closed under shortest paths from its root (proof of their Lemma 4.2). Hence T (C(w)) = v∈C(w) P (w, v) is a shortest-path tree rooted at w with vertex set C(w), which we call the cluster tree of w. All our schemes route along cluster trees, and the main difficulty is to choose a good tree to route on. Once the tree is chosen, the labeled tree routing of Thorup and Zwick [TZ01] routes along the tree path. Lemma 4 (Corollary 2.7 of [TZ01]). Let T be a tree on at most n vertices with fixed O(log n)-bit ports. We can assign every vertex v a label L(v, T ) of O(log2 n/ log log n) bits such that, given L(x, T ) and L(v, T ) for x ̸= v, the port of the first edge on the x–v path in T can be computed in constant time. We apply Lemma 4 to every cluster tree T (C(w)), with the ports of G. Lemma 5 (Lemma 16 of [KR25a]). If hi+1 (v) > d(u, v) + hi (u), then v ∈ C(pi (u)). A lower bound for randomized routing. The lower bound of Thorup and Zwick [TZ01] and Zinovyev [Zin22] is stated for deterministic routing. We adapt it to randomized routing, in which the routing tables and the labels are deterministic and only the routing uses coins. Lemma 6. Assume the Erdős girth conjecture. For every integer k ≥ 2 and every s < 2k − 1, every labeled routing scheme with randomized routing, expected stretch s, and labels of o(n1/(k−1) ) bits uses Ω(n1+1/(k−1) ) bits of total storage on some graph with n vertices. Proof. Zinovyev [Zin22, Theorem 8] proves the bound for deterministic routing, with fixed ports, by recovering the port assignment of a fixed graph of girth 2k with Ω(n1+1/(k−1) ) edges from the routing tables. For every edge (x, y), a route from x to y shorter than 2k − 1 traverses the edge itself, so simulating it reveals the port of x towards y. With expected stretch s, such a route has probability at least p = 2k−1−s 2k−2 > 0, ˆ since d(x, y) ≥ 1. The simulation does not send a message, so it may try any outcome of the coins. Among O(log n/p) random outcomes, fixed in advance, with high probability every edge has one that gives such a route, and naming it takes O(log log n) bits per edge, which is of lower order than the bound. So the simulation recovers the whole port assignment, and the bound holds. 6

pτ (v) pi (u)

v

u

Figure 1: The message always goes from u to pi (u) (black). It then takes the blue route if v ∈ C(pi (u)), and the green route otherwise. The dashed line is P (u, v).

3

Overview

In this section, we first describe the routing framework common to all of our schemes. We then present the key new ideas behind each of our results and explain the difficulties they overcome. The framework. All our schemes use the hierarchy of Thorup and Zwick [TZ05] (Section 2.1), and route along its cluster trees. In the labeled schemes, the label of a vertex v is L(v) = ⟨id(v), {⟨i, hi (v), id(pi (v)), L(v, T (C(pi (v)))), L(pi (v), T (C(pi (v))))⟩ | i ∈ [k]}⟩. Given L(v), the source u first checks whether v ∈ B(u) ∪ C(u), and if so, routes to v along a shortest path. Otherwise, let τ = min{i ∈ [k] | pi (v) ∈ B(u)} be the first level at which the pivot of v is in B(u). Then both u and v are in the cluster of pτ (v), and Thorup and Zwick [TZ01] route along T (C(pτ (v))), with stretch 4τ − 1 ≤ 4k − 5. We call pτ (v) the fallback pivot, and this route the fallback route. Chechik [Che13a] and Kadria and Roditty [KR25a] improve this stretch by first visiting pivots of the source. In a visit at level i, u routes to pi (u), and pi (u) checks whether v ∈ C(pi (u)). If so, the message continues to v along T (C(pi (u))). Otherwise, d(u, v) ≥ hi+1 (v) − hi (u) by Lemma 5, and we call hi+1 (v) − hi (u) the threshold of level i. The message then returns to u and takes the fallback route. So on failure, the message follows u → pi (u) → u → pτ (v) → v (Figure 1). The difficulty. Kadria and Roditty [KR25a] observed that if the source u knew d(u, v) in advance, it could get stretch 2k − 1. It would visit pi (u) for the first level i with hi+1 (v) − hi (u) > d(u, v), since then v ∈ C(pi (u)) by Lemma 5, or route through the fallback pivot if τ ≤ i. As in the distance oracle of Thorup and Zwick [TZ05], every level below the chosen one raises the heights by at most d(u, v), so the chosen level i has hi (u) ≤ i d(u, v). The source does not know d(u, v). It knows only lower bounds on d(u, v), from the labels and from failed visits, so it must choose which pivots to visit without knowing which visit succeeds. New routing techniques.

We overcome this difficulty with the following techniques.

• Randomized routing. Only the routing is randomized. The routing tables and the labels are fixed before the routing starts. We may view d(u, v) as chosen by an adversary that knows the tables, the labels, and the distribution of the route, but not the coin flips of the source, since d(u, v) is fixed with the graph before the source flips its coins. Against a deterministic choice, the adversary picks a distance at which the chosen route is long. Different routes are long at different distances, so a random choice prevents the adversary from picking a distance that is bad for all of them at once. For example, let k = 3, and suppose that the source knows that d(u, v) ≥ 2, h1 (u) = 2, and that the fallback pivot is p2 (v) with h2 (v) = 5. The fallback route has length up to d(u, v) + 2h2 (v), so its 7

stretch can be 6 at d(u, v) = 2. The visit at level 1 has threshold h2 (v) − h1 (u) = 3, so it can fail at d(u, v) = 3, and then the route has length up to 3 + 2h1 (u) + 2h2 (v) = 17, a stretch of 17/3. Both are above 2k − 1 = 5. A fair coin between the two has expected stretch at most 12 (6 + 3) = 4.5 at d(u, v) = 2, where the visit succeeds, and at most 12 (13/3 + 17/3) = 5 at d(u, v) = 3, where the visit fails. • Optimizing over all choices at once. In the labeled schemes and the deterministic name-independent schemes, the source bounds the cost of every possible choice before it sends the message, and solves an optimization problem over all levels at once, instead of comparing the levels one by one (Section 3.1). • Cheaper search in trees. With worst-case storage, a pivot cannot store its cluster, so a visit searches the cluster tree. We give a better search on trees, and search only a truncated tree (Section 3.2). We now describe these techniques for each model.

3.1

Labeled routing with average storage

We start with this model, which is the simplest. Every vertex u stores its bunch B(u) and its cluster C(u). e 1+1/k ) total storage, that is, O(n e 1/k ) on average. Its routing table is This takes O(n RT(u) = L(u) ∪ {⟨id(w), L(u, T (C(w)))⟩ | w ∈ B(u)} ∪ {⟨id(x), L(x, T (C(u)))⟩ | x ∈ C(u)}. e We use the preprocessing of Kadria and Roditty [KR25a], with O(k) additional words per vertex, and change only the routing phase. Our schemes visit a single pivot pi (u), for a level i ∈ [τ ], before the fallback route. Since p0 (u) = u, the level i = 0 means taking the fallback route directly. The key is to choose i, deterministically or at random, and to bound the resulting stretch. Choosing the level.

From RT(u) and L(v), the source immediately computes the lower bound o n
M = max h1 (v), max hi+1 (u) − hi (v) , max |hi (u) − hi (v)| ≤ d(u, v). 1≤i≤τ

0≤i<τ

The three terms are at most d(u, v) since v ∈ / C(u), since pi (v) ∈ / B(u) for i < τ , and by the triangle inequality (Section 4.3). ˆ v) − d(u, v) the extra cost, and the extra cost divided by d(u, v) the extra stretch. If the We call d(u, visit succeeds, the route has length hi (u) + d(pi (u), v) ≤ d(u, v) + 2hi (u). So the extra cost is at most 2hi (u), and the extra stretch is at most 2hi (u)/M . If the visit fails, the fallback route has length at most d(u, pτ (v)) + hτ (v) ≤ d(u, v) + 2hτ (v). So the extra cost of u → pi (u) → u → pτ (v) → v is at most 2hi (u) + 2hτ (v), and since d(u, v) is at least the threshold, the extra stretch is at most 2hi (u) + 2hτ (v) . max{M, hi+1 (v) − hi (u)} Thus, for every level i, the extra stretch is at most βi :   2hi (u) 2hi (u) + 2hτ (v) βi = max , . M max{M, hi+1 (v) − hi (u)} The source knows every term of βi , so it can compute βi for every level before visiting any pivot. In the deterministic case, we choose a level that attains β ∗ = mini∈[τ ] βi , and show that β ∗ ≤ τ / ln(3/2) ≤ (k − 1)/ ln(3/2) in Lemma 11. This gives stretch 1 + (k − 1)/ ln(3/2) (Theorem 2).

8

The randomized choice. Our randomized scheme flips coins only to choose the level i. We prove that, in expectation over the choice of i, ˆ v)] ≤ (2τ + 1)d(u, v) ≤ (2k − 1)d(u, v), E[d(u, which matches the lower bound that follows from the Erdős girth conjecture (Lemma 6). The source chooses the distribution over [τ ] that minimizes its largest expected extra stretch over all distances d ≥ M . The bound on the expected extra cost changes only when d crosses a threshold, and between thresholds the bound on the expected extra stretch decreases. Hence the source needs to consider only d = M and the O(k) thresholds. Thus it solves a linear program with O(k) variables and constraints, and samples i from an optimal distribution (Section 4.4). Why the value is at most 2τ . Fix a distance guess D ≥ M , and let i be the first level in {0, . . . , τ − 2} with hi+2 (u) − hi (u) > M + D, if such a level exists. By the definition of M , we have hi+2 (u) − hi+1 (v) ≤ M , and hence hi+1 (v) − hi (u) ≥ hi+2 (u) − hi (u) − M > D. Thus the visit at level i succeeds whenever d(u, v) ≤ D. Moreover, by the choice of i, every earlier increase over two levels is at most M + D. Summing these increases from level 0 or 1, according to the parity of i, and using h0 (u) = 0 and h1 (u) ≤ M , gives hi (u) ≤ 2i (M + D) ≤ iD. If no such level exists, the same summation gives hτ −1 (u) ≤ (τ − 1)D. If hτ (v) − hτ −1 (u) > D, visiting level τ − 1 succeeds whenever d(u, v) ≤ D, with extra cost at most 2(τ − 1)D. Otherwise, hτ (v) ≤ τ D, so the fallback route has extra cost at most 2τ D. Thus, if the source knew d(u, v), setting D = d(u, v) would give extra cost at most 2τ d(u, v). Now consider a distribution of distances d ≥ M , and a level i whose visit succeeds whenever d ≤ D. The visit contributes at most 2hi (u) to the extra cost, and it can require the fallback route only when d > D. Its expected extra cost is therefore at most 2hi (u) + 2hτ (v) Pr[d > D]. To obtain the bound 2τ E[d], after paying 2hi (u) for the visit, we have 2τ E[d] − 2hi (u) left for the expected fallback cost. Since the fallback contributes at most 2hτ (v), it suffices that Pr[d > D] ≤

τ E[d] − hi (u) . hτ (v)

We prove that, for every distribution of distances, some level has expected extra cost at most 2τ E[d], using the growth bounds above and treating the last level and the direct fallback route separately. By LP duality, this gives a distribution over levels whose expected extra cost is at most 2τ d for every d ≥ M , without knowing d(u, v) (Section B.1).

3.2

Labeled routing with worst-case storage

In this model, as in the scheme of Thorup and Zwick [TZ01], every vertex v stores only its bunch B(v) and e 1/k ) vertices by Lemma 2. A vertex can no longer store its level-0 cluster C0 (v) = C(v, A1 ), which has O(n its cluster. So in a visit, pi (u) cannot check whether v ∈ C(pi (u)). To solve this problem, Chechik [Che13a] distributed the cluster among the vertices of its tree T (C(pi (u))). Roughly speaking, the visit then solves name-independent routing on this tree: it reaches v if v ∈ C(pi (u)), and returns to pi (u) otherwise. We improve upon the routing scheme of Chechik [Che13a] with three ideas: 1. We improve the name-independent routing on trees, and search only in a truncated cluster tree. 2. We choose the level of the visit by considering all the levels at once, rather than one by one. 3. We choose this level at random, as with average storage.

9

Better name-independent routing on trees. Let T be an unweighted tree on N vertices, with root w and radius R, and let S ≥ 2. We give a name-independent routing scheme on T that finds the record of v, or determines that v ∈ / T , after a walk of length at most R + 2⌈logS N ⌉ − 2 from w (Lemma 12). Every e e vertex stores O(S) words, and O(1) words in expectation. Our idea is to randomize the construction of Abraham, Gavoille, and Malkhi [AGM04]. They store the N pairs ⟨id(x), L(x, T )⟩, sorted by name, at the first N/S vertices in a preorder of T , with an index that guides the search from w. They showed that the search for id(v) makes at most logS (N/S) excursions of two edges each. So reaching the pair of v takes at most R + 2 logS (N/S) steps, but the first N/S vertices of e the preorder store O(S) words each. We split the preorder into S consecutive blocks of about N/S vertices each, and store the pairs in a block chosen uniformly at random (see Figure 2). A vertex is in the chosen block with probability 1/S, and then e it stores O(S) pairs, so its expected storage is O(1). We need a random block since every vertex is in many cluster trees. A fixed block, such as the first one, can contain the same vertex in many of these trees, and e then this vertex stores O(S) words in each of them. A random block need not contain w. The ancestors of block vertices that lie outside the block lie on the path from w to the first vertex of the block, and the vertices of this path guide the search into the block, so the search keeps the same length bound. The main difficulty in adapting their construction is that a preorder prefix induces a connected subtree, whereas a random block may be disconnected. We must show that the path from w to the block can guide the search while preserving the search-length and storage bounds. e 1/k ) chosen so Truncated cluster trees. We apply this scheme to every cluster tree, with S = O(n i+1 that the cluster of every vertex of Ai \ Ai+1 has at most S vertices. The source visits only levels with hi+1 (u) > hi (u), so pi (u) ∈ Ai \ Ai+1 . Thus, in the cluster tree of a visited pivot, the search, including the return to the root, has length at most 2R + 2i. The problem is that the radius of T (C(pi (u))) can be much larger than hi (u) + d(u, v), and a search pays twice the radius. If hi+1 (v) > d(u, v) + hi (u), then v ∈ C(pi (u)) and d(pi (u), v) < hi+1 (v), so it suffices to search T (C(pi (u))) truncated at this radius. We do this as follows. For every w ∈ Ai \ Ai+1 , let Tj be the subtree of T (C(w)) induced by the min{2j , |C(w)|} vertices of C(w) closest to w, for j = 0, . . . , ⌈log2 |C(w)|⌉, breaking ties consistently. For j ≥ 1, we store the records ⟨id(v), L(v, T (C(w)))⟩, for v ∈ V (Tj ), and their search indices in the smaller tree Tj−1 , as before. The search then stays inside Tj−1 , which has a small radius, while still detecting every v ∈ V (Tj ). The pivot uses the first Tj that contains all cluster vertices at distance less than hi+1 (v) from it. The radius of Tj−1 is then less than hi+1 (v). Since Tj has at most twice as many vertices as Tj−1 , the expected storage contributed by each search e e structure remains O(1) per vertex, with worst-case storage O(S). At each level i, a vertex belongs to 1/k e O(n ) clusters, each with O(log n) such structures. The blocks of different search structures are chosen e 1/k ) words, and we repeat the choice of the independently, so with high probability, every vertex stores O(n blocks until this holds. The routing phase. The source computes M as before. Only the cost of a visit to pi (u) changes. After routing to pi (u), the message searches in Tj−1 , with Tj chosen as above. The search, including the return to pi (u), has length at most 2hi+1 (v) + 2i. If the search succeeds, the message continues to v along a path of length d(pi (u), v). If it fails, then d(u, v) ≥ hi+1 (v) − hi (u) as before, and the message returns to u and takes the fallback route. Thus, a visit at level i has extra stretch at most   2hi (u) + 2hi+1 (v) + 2i + 2hτ (v) 2hi (u) + 2hi+1 (v) + 2i , . βi = max M max{M, hi+1 (v) − hi (u)} As with average storage, the source computes the bound βi for every level before visiting any pivot, and visits a single pivot, chosen deterministically or at random. The source also chooses the search radius, which may 10

be smaller than hi+1 (v). A search of radius hi (u) + t, for M < t ≤ hi+1 (v) − hi (u), costs 4hi (u) + 2t + 2i, and 8 a failure shows that d(u, v) ≥ t. The coefficients 1+4 ln(3/2) and 83 are the values of the resulting optimizations (Lemmas 13 and 14).

3.3

Name-independent routing

In this model, u gets only id(v), and there are no labels. This causes two difficulties. First, u cannot route through the pivots of v, since it does not know them. Intuitively, a vertex that could tell u the pivots of v would store a map from id(v) to a label of v, and could then route to v by itself. Second, u cannot compute the lower bound M , since it does not know the heights of v. It knows only that d(u, v) ≥ h1 (u) if v ∈ / B(u). Random scales. We change the routing phase to visit a sequence of pivots pi (u), in increasing order of level, until a visit succeeds. The source guesses d(u, v) at geometrically increasing scales D ≥ h1 (u), and for each scale, it visits the pivot of the first level i whose gap hi+1 (u) − hi (u) exceeds 2D. If d(u, v) ≤ D, then hi+1 (v) ≥ hi+1 (u) − d(u, v) > hi (u) + d(u, v), so this visit succeeds by Lemma 5. Hence each failure shows that d(u, v) > D. With randomization, the scales are ej+X , for j ∈ Z, where the shift X is uniform in [0, 1) and drawn once per message. In expectation, the first gap h1 (u) ≤ d(u, v) costs at most 2d(u, v), and every other gap costs at most 4d(u, v). With the final route of length d(u, v), this gives expected stretch 1 + 2 + 4(k − 2) = 4k − 5 (Theorem 5). Deterministic scales. Deterministically, the source picks the sequence of levels with the smallest worstcase bound. Let λ = 1/(21/(k−1) − 1) and let i1 < · · · < im be the levels of the sequence. If hi1 (u) + · · · + hit (u) ≤ λ (hit−1 +1 (u) − hit−1 (u)) for every t ≥ 2, then the extra stretch is at most 4λ, since the source continues past a level only if 2d(u, v) is at least its gap. We show that such a sequence always reaches level k − 1. This gives stretch 1 + 4λ ≤ 1 + 4(k − 1)/ ln 2 ≈ 5.77k (Theorem 6), and this is tight: when the gaps are 2i/(k−1) , no sequence does better. Worst-case storage. With worst-case storage, a visit searches the cluster tree of pi (u) as in the labeled schemes. The source does not know hi+1 (v), so the radius of the search is hi (u) + D, given by the current guess D. A failed search costs 4hi (u) + 2D + 2i, so the guesses now also pay for the radius. This gives (8k + 2e − 7, 2k − 2)-expected stretch and stretch ≈ 11.54k (Theorems 7 and 8).

3.4

Weighted graphs

Our average-storage schemes work in weighted graphs with the same bounds. With worst-case storage, the search in a cluster tree makes up to i + 1 excursions of two edges each, so in a tree with maximum edge weight W it costs up to 2(i + 1)W more than in an unweighted tree. Since W can be as large as the radius of the tree, a search at level i may cost Θ(i) times its radius. To avoid this, for every j ≥ 0 with Wj−1 at most the diameter, we preprocess the graph Gj that contains only the edges of weight at most Wj = (1 + ε)j . This multiplies the storage by O(ε−1 log ∆). If the source knew d(u, v), it could route in Gj for the smallest j with Wj ≥ d(u, v). This graph contains a shortest path from u to v, and every excursion costs at most 2(1 + ε)d(u, v). The source does not know d(u, v), and a small Wj makes the search cheaper, but it may make the distance in Gj larger, or disconnect u from v. Our routing chooses the level and the graph jointly, using the heights in all the graphs Gj (Section F).

4

Labeled routing with average storage

e 1/k ) average local storage, and prove TheIn this section, we present our labeled routing schemes with O(n orems 1 and 2. Both schemes use the same preprocessing (Section 4.1) and the same routing framework (Section 4.2). The source either routes directly to the destination in T (C(v)) or T (C(u)), or first visits one

11

of its own pivots. If the destination is not in that pivot’s cluster, the message returns to the source and routes to the destination in the cluster tree of one of the destination’s pivots. The two schemes differ only in which pivot the source visits (Section 4.3). We present the randomized choice first (Section 4.4) and then the deterministic one (Section 4.5). The proofs of the two optimization bounds are in Section B.

4.1

Preprocessing

e We use the preprocessing of Kadria and Roditty [KR25a], with O(k) additional words per vertex. We compute the deterministic hierarchy of Lemma 1 and the tree labels of Lemma 4 for every cluster tree. The label of a vertex v ∈ V is L(v) = ⟨id(v), {⟨i, hi (v), id(pi (v)), L(v, T (C(pi (v)))), L(pi (v), T (C(pi (v))))⟩ | i ∈ [k]}⟩. The routing table of a vertex u ∈ V contains its label and the following two separately tagged parts: RT(u) = L(u) ∪ {⟨id(w), L(u, T (C(w)))⟩ | w ∈ B(u)} ∪ {⟨id(x), L(x, T (C(u)))⟩ | x ∈ C(u)}. The label L(u) gives the pivot distances and the pivots of u, and the labels needed to route to the pivots. The two parts are separate dictionaries keyed by identifiers. The first part gives the bunch membership test at u and the label of u in every cluster tree that contains u. The second part gives the cluster membership test at u and the labels of the vertices of C(u) in T (C(u)). P e 1+1/k ), and |L(u)| = O(k) e Lemma 7. for every u ∈ V . u∈V |RT(u)| = O(n e e e Proof. Every tree label has O(1) words, so |RT(u)| = O(|B(u)| + |C(u)| + k) and |L(u)| = O(k). The total P P 1+1/k e bound follows from u |C(u)| = u |B(u)| = O(n ) and k ≤ log n.

4.2

The routing framework

Fix a source u and a destination v ̸= u for the rest of this section. The naive case. If v ∈ B(u), then u routes to v in T (C(v)), using the level-0 tree label in L(v). If v ∈ C(u), then u routes to v in T (C(u)), using the tree label in RT(u). In both cases, the message follows a shortest path. For the rest of the section, we assume that v ∈ / B(u) ∪ C(u). The general case. Let τ = min{i ∈ [k] | pi (v) ∈ B(u)} be the fallback level. Using RT(u) and L(v), the source u computes a level i = PickLevel(u, v) ∈ [τ ]. We define PickLevel in Sections 4.4 and 4.5. Then u routes to pi (u) in T (C(pi (u))), and pi (u) checks, using RT(pi (u)), whether v ∈ C(pi (u)). If so, pi (u) routes to v in T (C(pi (u))), using the tree label of v stored in RT(pi (u)). Otherwise, the message returns to u in T (C(pi (u))), and u routes to v in T (C(pτ (v))). We call this last route the fallback route. Since T (C(pτ (v))) is a shortest-path tree rooted at pτ (v), the fallback route has length at most d(u, pτ (v)) + hτ (v). For i = 0, we have p0 (u) = u and v ∈ / C(u), so the message takes the fallback route directly. See Algorithm 1 and Figure 1. Next, we show that every vertex on the routing walk has the information it needs. To route in a cluster tree T (C(w)) towards a target y, the header contains id(w) and L(y, T (C(w))). Lemma 8. For every w ∈ V and every vertex z of T (C(w)), L(z, T (C(w))) ∈ RT(z). Proof. The vertex set of T (C(w)) is C(w) (Section 2.1), so z ∈ C(w) and w ∈ B(z). Hence L(z, T (C(w))) is in the first part of RT(z), keyed by id(w). 12

Algorithm 1: Route(u, v) if v ∈ B(u) then Route u ⇝ v in T (C(v)); 3 return;

1

2

if v ∈ C(u) then Route u ⇝ v in T (C(u)); 6 return;

4

5

τ ← min{i ∈ [k] | pi (v) ∈ B(u)}; i ← PickLevel(u, v); 9 Route u ⇝ pi (u) in T (C(pi (u))); 10 if v ∈ C(pi (u)) then // tested at pi (u) 11 Route pi (u) ⇝ v in T (C(pi (u))); 12 return; 7

8

13 14

Route pi (u) ⇝ u in T (C(pi (u))); Route u ⇝ v in T (C(pτ (v)));

Every vertex on the walk can compute the next port by Lemma 4. The label of pi (u) in T (C(pi (u))) is in L(u), which is stored in RT(u), the label of v in T (C(pi (u))) is in the second part of RT(pi (u)), and the label of v in T (C(pτ (v))) is in L(v). The return label is given by Lemma 8. The header contains, besides e L(v), only i, the current tree identifier and target label, and the return label, that is, O(1) words.

4.3

Choosing the level

We first describe what the source knows when it chooses i: a lower bound M on d(u, v), and a bound on the cost of each choice of i. Then we define and analyze the randomized PickLevel, followed by the deterministic one. The source does not know d(u, v). To choose i, it computes  
M = max h1 (v), max hi+1 (u) − hi (v) , max |hi (u) − hi (v)| , 0≤i<τ

1≤i≤τ

which is a lower bound on d(u, v). Indeed, h1 (v) ≤ d(u, v) since v ∈ / C(u). By the minimality of τ , pi (v) ∈ / B(u) for 0 ≤ i < τ , so hi+1 (u) ≤ d(u, pi (v)) ≤ d(u, v) + hi (v). Finally, |hi (u)
− hi (v)| ≤ d(u, v)
by the triangle inequality. Summing h1 (v) ≤ M and hi+1 (v)−hi (v) = hi+1 (v)−hi+1 (u) + hi+1 (u)−hi (v) ≤ 2M for 1 ≤ i < τ gives hτ (v) ≤ (2τ − 1)M . Together, 0 < hτ (v) ≤ (2τ − 1)M

and

M ≤ d(u, v).

(1)

If the source chooses i ∈ [τ ], then ˆ v) ≤ d(u, v) + 2hi (u) + 2hτ (v) · 1[d(u, v) ≥ hi+1 (v) − hi (u)], d(u,

(2)

where 1[·] is the indicator function. Indeed, the message first travels hi (u) to pi (u). If v ∈ C(pi (u)), it then travels d(pi (u), v) ≤ hi (u) + d(u, v). Otherwise, d(u, v) ≥ hi+1 (v) − hi (u) by Lemma 5, and the message travels hi (u) back to u and then at most d(u, pτ (v)) + hτ (v) ≤ d(u, v) + 2hτ (v) along the fallback route. The first extra term pays for the pivot visit, and the second for the fallback. The source knows every term of this bound except d(u, v). Below, d ≥ M denotes a possible value of d(u, v). Both choices need only consider the possible values Θ = {M } ∪ {hi+1 (v) − hi (u) | i ∈ [τ ], hi+1 (v) − hi (u) > M }. 13

Indeed, let θ < θ′ be consecutive values of Θ, or θ = max Θ and θ′ = ∞. Every indicator 1[d ≥ hi+1 (v)−hi (u)] is constant for d ∈ [θ, θ′ ). For each level, the bound 2hi (u) + 2hτ (v) · 1[d ≥ hi+1 (v) − hi (u)] on the extra cost is constant on this interval, as is its expectation under any distribution over the levels. After dividing by d, each resulting bound on the extra stretch, or on the expected extra stretch under a distribution, is maximized on the interval at d = θ. Since M = min Θ, these intervals cover all d ≥ M , so each bound attains its maximum over d ≥ M in Θ.

4.4

Randomized PickLevel

We now define the randomized PickLevel, which samples a level to minimize the worst-case expected extra stretch. Theorem 1. For every integer k ≥ 2, there is a (2k − 1)-expected stretch labeled compact routing scheme e 1/k ) words, labels of O(k) e e that uses average local storage of O(n words, and headers of O(1) words. Let P(X) denote the set of distributions over a finite set X. The source solves   X
πi 2hi (u) + 2hτ (v) · 1[d ≥ hi+1 (v) − hi (u)] ≤ zd for every d ∈ Θ, z ∗ = min z  i∈[τ ]

  π ∈ P([τ ]) . (3) 

This linear program has O(k) variables and constraints.6 Given an optimum (π ∗ , z ∗ ), PickLevel(u, v) returns i with probability πi∗ . This is the only random choice during routing. Stretch analysis. ˆ v)] ≤ (1 + z ∗ )d(u, v). Lemma 9. E[d(u, Proof. By the choice of Θ, the constraint of (3) for π ∗ and z ∗ holds for every d ≥ M , not only for d ∈ Θ. Since d(u, v) ≥ M , the claim follows from (2) by taking the expectation over i. The following lemma bounds the value of the linear program and yields the desired expected stretch. Lemma 10. z ∗ ≤ 2τ . Proof. The proof is deferred to Section B.1. We now prove Theorem 1. Proof of Theorem 1. Lemma 7 bounds the storage and the labels. By Lemma 8, every vertex on the walk e computes the next port, so the message is always delivered, with headers of O(1) words besides L(v). The naive case has stretch 1. Otherwise, by Lemma 9 and Lemma 10, ˆ v)] ≤ (1 + z ∗ )d(u, v) ≤ (2τ + 1)d(u, v) ≤ (2k − 1)d(u, v). E[d(u,

4.5

Deterministic PickLevel

We now define the deterministic PickLevel, which chooses the level with the smallest worst-case extra stretch.
k−1 Theorem 2. For every integer k ≥ 2, there is a 1 + ln(3/2) ≈ 2.47k − 1.47 -stretch labeled compact routing e 1/k ) words, labels of O(k) e scheme with deterministic routing that uses average local storage of O(n words, and e headers of O(1) words. 6 The coefficients are rational under our weight convention, allowing an exact rational optimum and exact sampling with random bits. Source computation is unrestricted.

14

For i ∈ [τ ], let  βi = max

2hi (u) + 2hτ (v) 2hi (u) , M max{M, hi+1 (v) − hi (u)}

 ,

and let β ∗ = mini∈[τ ] βi . The deterministic PickLevel(u, v) returns a level attaining β ∗ . Stretch analysis. By the choice of Θ and (2), choosing such a level gives stretch at most 1 + β ∗ . The following bound therefore suffices. Lemma 11. β ∗ ≤ τ / ln(3/2). Proof. The proof is deferred to Section B.2. Proof of Theorem 2. The storage, label, and header bounds follow as in the proof of Theorem 1. The naive case has stretch 1. Otherwise, Lemma 11 gives stretch at most 1 + β∗ ≤ 1 +

k−1 τ ≤1+ . ln(3/2) ln(3/2)

For the bound 4k−5, level 0 is the fallback route (p0 (u) = u). Since h0 (u) = 0 and h1 (v)−h0 (u) = h1 (v) ≤ M , we have β ∗ ≤ β0 = 2hτ (v)/M ≤ 2(2τ − 1) by (1), giving stretch at most 4τ − 1 ≤ 4k − 5. For every k ≥ 3, this improves the previous bound of Kadria and Roditty [KR25a]. The comparison is in Section B.3. The profile in Section B.4 shows that the coefficient 1/ ln(3/2) cannot be improved using only the inequalities of our analysis.

5

Labeled routing with worst-case storage

e 1/k ) local storage at every vertex in unIn this section, we present our labeled routing schemes with O(n weighted graphs, and prove Theorems 3 and 4. We use the routing framework of Section 4, and Section 3.2 describes the changes. The main difference is that a pivot can no longer store its cluster, so testing whether the destination is in the cluster requires a search in the cluster tree. We first give a name-independent routing scheme on trees (Section 5.1), and use it to construct the routing tables (Section 5.2). Our two schemes use the same preprocessing and differ only in the choice of the visited pivot. We present the deterministic choice (Section 5.3) and then the randomized one (Section 5.4).

5.1

Name-independent routing on trees

Lemma 4 requires the label of the destination. In our schemes with worst-case storage, a message reaches the root of a cluster tree with only the identifier of the destination. Abraham, Gavoille, and Malkhi [AGM04] give a name-independent routing scheme on trees that trades worst-case local storage for additive stretch. e e For a parameter S, a vertex in their scheme stores up to O(S) words, and the vertices of the tree store O(1) words on average. This average bound is not enough for us. Every vertex is in many cluster trees, and the e same vertex could store O(S) words in many of them. We therefore use a randomized variant, in which every e vertex stores O(1) words in expectation. The expected storage of a vertex then adds up over the trees that contain it. Definition 1. Let T be a tree rooted at w. A randomized S-name-independent routing scheme on T receives only id(v) at w. If v ∈ V (T ), it finds L(v, T ) and routes the message to v. Otherwise, it determines that v∈ / V (T ) and returns the message to w. We denote by dˆT (w, v) the total length of this walk. Each vertex e e stores at most O(S) words for every outcome of the preprocessing, and O(1) words in expectation over the preprocessing randomness.

15

We use such a scheme on a cluster tree to test whether the destination is in the cluster, and if so, to route to it. Lemma 12. Let T be an unweighted tree on N ≥ 2 vertices, with root w and radius R = maxx∈V (T ) dT (w, x). e For every integer 2 ≤ S ≤ N , there is an O(S)-name-independent routing scheme on T such that, for every name id(v), ( 3R + 2⌈logS N ⌉ − 2, v ∈ V (T ), dˆT (w, v) ≤ 2R + 2⌈logS N ⌉ − 2, v ∈ / V (T ). Moreover, the record of v is found, or its absence is determined, after a walk of length at most R+2⌈logS N ⌉−2 from w. The search first locates the record ⟨id(v), L(v, T )⟩ associated with the destination name. We distribute these records among a subset of the vertices and store indices that guide the search from w. Once the record is found, the message uses L(v, T ) to reach v. Preprocessing. Let N = |V (T )|, and let 2 ≤ S ≤ N be the parameter from Lemma 12. We first compute the tree-routing labels L(v, T ). Each vertex stores its own label, and every nonroot vertex stores the port leading to its parent. Fix an ordering of the children of each vertex and compute a preorder traversal of T . Partition this order into S consecutive blocks whose sizes differ by at most one, and choose one block uniformly at random. Let X be its set of vertices. The set X contains Θ(N/S) vertices, which will each store O(S) records. The random choice is used to balance the expected storage among the vertices. Let x be the first vertex of X in the preorder, let P be the path from w to x, and let T ′ = T [X ∪ V (P )]. Since X is a consecutive preorder block, every ancestor of a vertex of X that lies outside X belongs to P . Thus, T ′ is a rooted subtree containing w and X. We now order the children in T ′ for the placement of records. At each vertex of V (P ) \ X, place the child continuing along P first, and order the remaining children by decreasing number of vertices of X in their subtrees. At each vertex of X, order all children by the same quantity. This second preorder determines the placement of records on the already chosen set X. Sort the records ⟨id(v), L(v, T )⟩, for v ∈ V (T ), by name and partition them into |X| consecutive groups whose sizes differ by at most one. Assign these groups, in order, to the vertices of X encountered by the second preorder. The records stored in each subtree of T ′ therefore form a consecutive part of the sorted list. Each vertex u ∈ V (T ′ ) stores the interval I(u) from the smallest to the largest name stored in its subtree. To choose among the children of a vertex, we use an index whose tables are distributed among the vertex and its children. This avoids storing the complete list of child intervals at the parent. Children with larger subtrees receive shorter words in the following encoding, so that reaching them requires fewer index lookups. For an ordered list of children, encode the first S children by one-digit words over {0, . . . , S − 1}, the next S 2 by two-digit words, and so on. Within each group, assign words in lexicographic order. For each word length, the representative of a nonempty prefix is the first child with that prefix. The prefix’s interval spans the names stored in the subtrees of all children with that prefix. The root table lists the intervals, representatives, and word lengths of all first-digit prefixes. For each proper prefix of a word, store at its representative a table listing its nonempty one-digit extensions. Each entry includes the corresponding interval and the port leading from the parent to its representative. At a vertex of X, build this index for all its children in T ′ , and store the root table locally. At a vertex of V (P ) \ X, handle the child continuing along P separately. Build an index for the remaining children in T ′ and, if any exist, store its root table at one of them. These children belong to X. The vertex itself stores the interval and port of the child continuing along P , and the port leading to the root-table holder, if one exists. Routing. The search starts at w with the destination name id(v). During the search, the message either searches the current subtree or reads a table in a child index. In the latter case, it records the vertex whose 16

w 1

2

13

3

4

7

5

6

8

x

10

9

11

14

15

17

16

18

19

20

12

x

Original preorder: 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

chosen block X path P from w to x

vertex in X

vertex in V (P ) \ X

Figure 2: Selecting a consecutive preorder block for N = 20 and S = 4. Numbers on vertices give their positions in the original preorder. The chosen block is X = {6, 7, 8, 9, 10}, its first vertex is x = 6, and P = (1, 2, 3, 6). w 1

2 I(2) = [a1 , a20 ] [a1 , a4 ] → 3 Otherwise: 7 (index)

7

3

Records: a5 , . . . , a8 I(7) = [a5 , a16 ]

10

Index of 2: [a5 , a16 ] → 7, [a17 , a20 ] → 10

Records: a17 , . . . , a20 I(10) = [a17 , a20 ]

Own index: [a9 , a12 ] → 8, [a13 , a16 ] → 9

6

8

9

x

Figure 3: The subtree T ′ = T [X ∪ V (P )] from Figure 2, with storage shown at vertices 2, 7, 10. Here a1 < · · · < a20 are the sorted names. Each record includes its routing label. Vertex 7 stores its own root table and that of vertex 2.

17

children are being indexed and whether it is reading the root table or a table for a specified word length and prefix. When the search is at u (and not reading an index table), it first checks whether id(v) ∈ I(u). If not, report failure. If u ∈ X, check its stored records. If the destination’s record is found, use L(v, T ) to deliver the message to v along the shortest path in T . Otherwise, read the local root table to choose among the children of u. If u ∈ V (P ) \ X, compare id(v) with the interval of the child continuing along P . If it belongs to that interval, forward the message to that child. Otherwise, move to the designated child holding the root table for the remaining children. If no such child exists, report failure. Within an index, use the destination name to select a matching entry in the root table and then refine the selected prefix using the corresponding tables. Tables stored at the current vertex are read locally. To reach a representative from its parent, traverse the edge leading to that child. To move between two children of the same parent, follow the two-edge path through the parent. The message carries the outgoing port to use upon returning to the parent and remains in the index-reading mode throughout this transition. Once a complete word is identified, resume the subtree search at the child encoded by that word. If no interval matches the destination name in a consulted table, report failure. Upon failure, return the message to w by following parent ports. e e Proof of Lemma 12. Every vertex stores O(1) words outside X and O(S) words inside X. Since each vertex e belongs to X with probability 1/S, its expected storage is O(1). We now bound dˆT (w, v). Let m(u) be the number of vertices of X in the subtree of T ′ rooted at u. Thus m(w) = |X|, and m(u) ≥ 1 throughout T ′ . Since the records are ordered by name, every interval test preserves the destination’s record if it exists. The search therefore ends either at its holder or with a correct report of absence. The search follows a descending path, with excursions to other children to read index tables. Each excursion traverses one edge in each direction. We bound their number as in [AGM04], using m(u) in place of the subtree size. Consider an index at u that selects a child y whose word has length ℓ. Reading the successive prefixes requires at most ℓ − 1 excursions before reaching y. For ℓ ≥ 2, the rank of y in the indexed list is at least 1 + S + · · · + S ℓ−1 > S ℓ−1 . Since these children are ordered by decreasing m, m(y) < m(u)/S ℓ−1 . If the search fails inside the index, take y to be the last representative visited. Its word belongs to the same length group, and at most ℓ − 1 excursions precede it, so the same argument applies. Failure at a locally stored root table adds no excursion. Reading a root table stored at a child of a vertex in V (P ) \ X may cause one additional excursion. This happens at most once: after leaving P through an indexed child, the search stays in a subtree contained in X. Let q count the excursions other than this possible additional one. Each index contributing a positive number of excursions decreases m by a factor strictly greater than S raised to the power of that number. Along the remaining descending edges, m does not increase. Since m starts at |X| and remains at least one, S q < |X| whenever q > 0. It follows that q ≤ ⌈logS |X|⌉ − 1. Including the possible additional excursion gives at most ⌈logS |X|⌉ excursions. The balanced partition gives |X| ≤ ⌈N/S⌉ ≤ S ⌈logS N ⌉−1 , so there are at most ⌈logS N ⌉ − 1 excursions, each of length 2. The descending path has length at most R, so the record of v is found, or its absence is determined, after a walk of length at most R + 2⌈logS N ⌉ − 2. If v ∈ V (T ), the message then reaches v in T after at most 2R more steps. Otherwise, it returns to w after at most R more steps.

18

5.2

Preprocessing

We compute the hierarchy of Lemma 2, and let S = 4⌈n1/k ⌉, so every cluster of a vertex of Ai \ Ai+1 has at most S i+1 vertices. Every vertex u stores L(u) and the first part of RT(u) from Section 4.1, with the labels as defined there. Instead of the second part, u stores C0 (u), which has O(S) vertices, as a dictionary of tree labels in T (C0 (u)). For each cluster tree T (C(w)), order its vertices by distance from w, breaking ties consistently. Let Tj be the subtree induced by the first min{2j , |C(w)|} vertices, for 0 ≤ j ≤ ⌈log2 |C(w)|⌉. For each j ≥ 1, distribute the records {⟨id(v), L(v, T (C(w)))⟩ : v ∈ V (Tj )} among the vertices of Tj−1 , using the construction of Lemma 12. Thus, the search takes place in Tj−1 , but determines whether v ∈ V (Tj ). Since |V (Tj )| ≤ 2|V (Tj−1 )|, each record holder stores at most twice as many records as before. The index construction and the search bound are unchanged. All records use labels for the full cluster tree T (C(w)). If |V (Tj−1 )| ≤ S, store the records of Tj directly at w. The record for T0 = {w} is also stored at w. For each j, the root stores the distance to the first cluster vertex outside Tj , or ∞ if there is none. Given a radius, it can therefore select the first Tj containing every cluster vertex strictly within that radius. e 1/k ) Choose the preorder blocks independently for different search structures. Each vertex belongs to O(n e cluster trees, each with O(log n) such structures. Each structure contributes O(1) expected words and at 1/k e e most O(S) words to a vertex. Independence and concentration give O(n ) storage at every vertex with high probability. The explicit dictionaries and the information stored at each root fit the same bound. We repeat the block choices if this bound is exceeded.

5.3

Deterministic routing

Theorem 4. For every integer k ≥ 2, there is a

8k 1+4 ln(3/2) + 1 ≈ 3.05k + 1 -stretch labeled compact routing e 1/k

scheme for unweighted graphs with deterministic routing that uses worst-case local storage of O(n e e labels of O(k) words, and headers of O(1) words.

) words,

If v ∈ B(u) ∪ C0 (u), route to v along a shortest path. Otherwise, compute τ and M as in Section 4.3, where v ∈ / C0 (u) gives h1 (v) ≤ d(u, v). The source chooses either the fallback route or a single visit to pi (u), for 1 ≤ i < τ . Let δi = hi+1 (v) − hi (u) be the threshold of level i and H = hτ (v). We consider only levels with δi > M . For a level with δi ≤ M , the visit may fail already when d(u, v) = M , so its bound exceeds that of the fallback route. For every considered level, hi+1 (u) ≥ hi+1 (v) − M > hi (u). Hence pi (u) ∈ Ai \ Ai+1 , so its cluster has at most S i+1 vertices. The cost of a visit. The message first routes to pi (u). The pivot selects the first Tj containing every vertex of its cluster at distance less than hi+1 (v). If j = 0, it checks the record locally. Otherwise, it searches for id(v) using the structure stored in Tj−1 . By the minimality of j, every vertex of Tj−1 is at distance less than hi+1 (v) from the pivot. Since distances are integers, the radius of Tj−1 is at most hi+1 (v) − 1. By Lemma 12 with R ≤ hi+1 (v) − 1 and ⌈logS |V (Tj−1 )|⌉ ≤ i + 1, the walk from the pivot to the record holder has length at most hi+1 (v) + 2i − 1. On success, the message uses the retrieved label to reach v. The distance from the record holder to v is at most hi+1 (v) − 1 + d(pi (u), v), so the total route length is at most hi (u) + 2hi+1 (v) + 2i − 2 + d(pi (u), v) ≤ d(u, v) + 2hi (u) + 2hi+1 (v) + 2i − 2.

19

On failure, the message returns to u and takes the fallback route in T (C(pτ (v))). The total route length is then at most d(u, v) + 2hi (u) + 2hi+1 (v) + 2i − 2 + 2hτ (v). A failure implies d(u, v) ≥ δi . Indeed, below this threshold, v belongs to the cluster by Lemma 5, and its distance from the pivot is less than hi+1 (v), so v ∈ V (Tj ). Combining the two cases gives ˆ v) ≤ d(u, v) + 2hi (u) + 2hi+1 (v) + 2i − 2 + 2H 1[d(u, v) ≥ δi ]. d(u, Choosing the visit and the radius. The search radius need not be hi+1 (v). For each 1 ≤ i < τ , the source considers every integer distance guess t with M < t ≤ δi . For this choice, the pivot searches the first Tj containing all cluster vertices at distance less than hi (u) + t. The guess t = δi gives the visit above. The search takes place in Tj−1 , whose radius is at most hi (u) + t − 1, since distances are integers. Thus the extra cost is at most 4hi (u) + 2t + 2i − 2 on success, and at most 4hi (u) + 2t + 2i − 2 + 2H on failure. Failure implies d(u, v) ≥ t. The source therefore minimizes      2H 4h (u) + 2t + 2i − 2 4h (u) + 2t + 2i − 2 + 2H i i , min max , . β ∗ = min 1≤i<τ  M M t t∈Z, M <t≤δi

The first choice is the fallback route. The resulting stretch is at most 1 + β ∗ . Lemma 13. Let

8

cM =

1 + (4 + 1/M )

3M X r=2M +1

Then β ∗ ≤ cM τ + 2 +

cM (M − 1) , 4M + 2

cM ≤

. 1 r 8 . 1 + 4 ln(3/2)

Proof. The proof is deferred to Section C. e 1/k ) words at every vertex by Section 5.2, and the labels and Proof of Theorem 4. The tables have O(n headers are as in Section 4. Let c = 8/(1 + 4 ln(3/2)). By Lemma 13 and τ ≤ k − 1, the stretch is at most   M −1 1 + β ∗ ≤ cM τ + + 3 ≤ c(k − 3/4) + 3 < ck + 1, 4M + 2 M −1 1 using cM ≤ c and 4M +2 < 4 for the second step, and c > 8/3 for the last step.

5.4

Randomized routing

Theorem 3. For every integer k ≥ 2, there is a ( 83 k + 6, 94 k)-expected stretch labeled compact routing scheme e 1/k ) words, labels of O(k) e for unweighted graphs that uses worst-case local storage of O(n words, and headers e of O(1) words. We use the same visits as in the deterministic scheme. The source chooses either the fallback route or a pair (i, t), where 1 ≤ i < τ and M < t ≤ δi is an integer. The pair (i, t) specifies a visit to pi (u) with search radius hi (u) + t. As proved above, its extra cost is at most 4hi (u) + 2t + 2i − 2 + 2H 1[d ≥ t], where d = d(u, v). The fallback route has extra cost at most 2H.

20

Let

8d + 4 d. 3d + 1 4d We bound the term 2t − 2 ≤ 6M − 2 separately and measure d by γ(d) ≈ 83 d. Since γ(d) = 38 d + 3(3d+1) ≤ 8 4 4 3 d+ 9 , this gives the bound and the additive 9 k of Lemma 14. The source minimizes z ≥ 0 over distributions π0 , πi,t on the available choices, subject to X
2Hπ0 + πi,t 4hi (u) + 2t + 2i − 2 + 2H 1[d ≥ t] ≤ zγ(d) + 6M − 2 (4) γ(d) =

i,t

for every integer M ≤ d ≤ 3M . Here π0 is the probability of taking the fallback route. Since every available guess satisfies t ≤ 3M (indeed, t ≤ δi = hi+1 (v)−hi (u) ≤ (hi+1 (u)+M )−hi (u) ≤ (hi (v)+2M )−hi (u) ≤ 3M ), the left-hand side is constant for d ≥ 3M . As γ is increasing, the constraints therefore hold for every integer d ≥ M. Lemma 14. The optimal value z ∗ of (4) satisfies 1 z∗ ≤ τ + . 2 Consequently, for d = d(u, v), ˆ v)] ≤ E[d(u,



   8 4 8d + 4 k+6 d≤ k + 6 d + k. 3d + 1 3 9

The expectation is over the source’s choice, with the preprocessing fixed. Proof. The proof is deferred to Section C. Proof of Theorem 3. The storage, label, and header bounds are as in the proof of Theorem 4. By the second ˆ v)] ≤ ( 8 k + 6)d(u, v) + 4 k. inequality of Lemma 14, E[d(u, 3 9

6

Name-independent routing with average storage

In this section, we present our name-independent schemes with average storage: a randomized scheme with expected stretch 4k − 5, and a deterministic scheme with stretch ≈ 5.77k. Both improve the 96k stretch of Abraham, Gavoille, and Malkhi [AGM04] by a factor of more than 16.

6.1

Expected 4k − 5 stretch

Fix a source u and a destination v ̸= u for the rest of this section. In a name-independent scheme, the source u receives only the name id(v) of v. Thus it knows neither the pivots of v nor their heights, which the labeled schemes of Section 4 read from L(v). In particular, it can compute neither the fallback level τ of Section 4.2 nor the lower bound M of Section 4.3. Instead, the source visits several of its own pivots, in increasing order of level, until one of them has v in its cluster. It chooses these levels by guessing d(u, v) at randomly shifted geometric scales. Theorem 5. For every integer k ≥ 2, there is a (4k − 5)-expected stretch name-independent compact routing e 1/k ) words and headers of O(1) e scheme that uses average local storage of O(n words. Preprocessing. We use the routing tables of Section 4.1, and no labels. In the first part of RT(u), we also store L(w, T (C(w))) for every w ∈ B(u). This does not change the storage bound. The second part of RT(w) stores the whole cluster of w, keyed by identifiers. Hence, given only id(v), a pivot pi (u) can test whether v ∈ C(pi (u)), and if so, find L(v, T (C(pi (u)))). This is where we use average storage. With worst-case storage, a cluster cannot be stored at its root, and the same test needs a name-independent search in the cluster tree (Definition 1). 21

The naive case. If v ∈ B(u), then u ∈ C(v), and u routes to v in T (C(v)), using L(v, T (C(v))) from the first part of RT(u). If v ∈ C(u), then u routes to v in T (C(u)), as in Section 4.2. In both cases, the message follows a shortest path. For the rest of the section, we assume that v ∈ / B(u) ∪ C(u). Since v ∈ / B0 (u), we have h1 (u) ≤ d(u, v). (5) Visiting a pivot. In a visit at level i ∈ [k], as in Algorithm 1, the source routes to pi (u) in T (C(pi (u))), and pi (u) checks whether v ∈ C(pi (u)). If so, the visit succeeds, and pi (u) routes to v in T (C(pi (u))). Otherwise, the visit fails, and the message returns to u in T (C(pi (u))). Since T (C(pi (u))) is a shortest-path tree rooted at pi (u), a failed visit costs 2hi (u), and a successful visit costs hi (u) + d(pi (u), v) ≤ 2hi (u) + d(u, v). In the labeled schemes, a visit at level i fails only if d(u, v) is at least the threshold hi+1 (v) − hi (u) (Lemma 5). Here, the source does not know hi+1 (v). Instead, it uses the gap gi = hi+1 (u) − hi (u) of level i, which it knows. Lemma 15. If gi > 2d(u, v), then v ∈ C(pi (u)). Proof. By the triangle inequality, hi+1 (v) ≥ hi+1 (u) − d(u, v) > hi (u) + d(u, v), and Lemma 5 gives v ∈ C(pi (u)). If the distance were known.

For D > 0, let i(D) = min{i ∈ [k] | gi > 2D}

be the first level whose gap exceeds 2D. It is nondecreasing in D, and by its minimality, every gap below i(D) is at most 2D. Hence X X hi(D) (u) = gr ≤ gr · 1[gr ≤ 2D]. (6) r<i(D)

r<k−1

A source that knows d(u, v) could visit level i(d(u, v)). By Lemma 15, this visit succeeds. By (5), the first gap is g0 = h1 (u) ≤ d(u, v), and every other gap below i(d(u, v)) is at most 2d(u, v). So hi(d(u,v)) (u) ≤ (2k − 3)d(u, v), and the visit costs at most 2hi(d(u,v)) (u) + d(u, v) ≤ (4k − 5)d(u, v). Here a gap below the chosen level can be up to 2d(u, v), since the proof of Lemma 15 uses only hi+1 (v) ≥ hi+1 (u) − d(u, v), which loses d(u, v). No choice of levels, even with the knowledge of d(u, v), gets a better bound from Lemma 15. Indeed, if g0 = d(u, v) and all the other finite gaps equal 2d(u, v), the lemma guarantees success only at level k − 1, whose visit can cost 2hk−1 (u) + d(u, v) = (4k − 5)d(u, v). This matches the stretch 4k − 5 of the labeled scheme of Thorup and Zwick [TZ01]. Random scales. The source does not know d(u, v), so it guesses it at the geometric scales Dj = ej+X , for j ∈ Z, where X is uniform in [0, 1).7 By (5), the source skips the scales below h1 (u). Let i1 < · · · < im be the distinct values of i(Dj ), for j ∈ Z with Dj ≥ h1 (u). The source visits these levels in this order until a visit succeeds (Algorithm 2). As in the scheme of Kadria and Roditty [KR25a], the source visits a sequence of its pivots, and every failure raises a lower bound on d(u, v). Indeed, by Lemma 15, a failed visit at level i(Dj ) shows that d(u, v) > Dj . The shift X is the only random choice, and it plays the role of the random index in Section 4.4. The graph, and hence d(u, v), is fixed before the source samples X. With fixed scales, d(u, v) could lie just above a scale. Then the visit at this scale may fail, and the next scale is almost e times larger than d(u, v). With the random shift, the fractional part of ln d(u, v) − X is uniform in [0, 1), and we bound the cost averaged over it. 7 The levels depend only on how X compares with the fractional parts of ln g and of ln(g /2), for 1 ≤ r < k − 1, which the r 0 source determines exactly by drawing the bits of X one at a time.

22

Algorithm 2: Name-independent Route(u, id(v)) if v ∈ B(u) then Route u ⇝ v in T (C(v)); 3 return;

1

2

if v ∈ C(u) then Route u ⇝ v in T (C(u)); 6 return;

4

5

Sample X uniformly from [0, 1); Let i1 < · · · < im be the distinct values of i(ej+X ), for j ∈ Z with ej+X ≥ h1 (u); 9 for s = 1, . . . , m do 10 i ← is ; 11 Route u ⇝ pi (u) in T (C(pi (u))); 12 if v ∈ C(pi (u)) then // tested at pi (u) 13 Route pi (u) ⇝ v in T (C(pi (u))); 14 return; 7 8

15

Route pi (u) ⇝ u in T (C(pi (u)));

Stretch analysis. X

ˆ v) ≤ d(u, v) + 2 Lemma 16. d(u,

hi(Dj ) (u).

j∈Z: h1 (u)≤Dj <e·d(u,v) ∗

Proof. Let j be the smallest j with Dj ≥ d(u, v), so Dj < e · d(u, v) exactly for j ≤ j ∗ . By (5), Dj ∗ ≥ h1 (u). The gap of level i(Dj ∗ ) exceeds 2Dj ∗ ≥ 2d(u, v), so the visit at this level succeeds by Lemma 15. Hence every visited level is at most i(Dj ∗ ). Since i(D) is nondecreasing, every visited level is i(Dj ) for some j ≤ j ∗ with Dj ≥ h1 (u). The bound follows from the costs of the visits: 2hi (u) for every visited level i, plus d(u, v) for the successful visit. ˆ v)] ≤ (4k − 5)d(u, v). Lemma 17. E[d(u, Proof. Write d = d(u, v). For every nonnegative function φ on (0, ∞), since X is uniform in [0, 1), Z ∞ Z ∞ hX i XZ 1 φ(D) E φ(ej+X ) = dD. φ(ej+x ) dx = φ(et ) dt = D 0 −∞ 0 j∈Z

j∈Z

By Lemma 16 and this identity for φ(D) = hi(D) (u) · 1[h1 (u) ≤ D < e · d], Z e·d hi(D) (u) ˆ v)] ≤ d + 2 E[d(u, dD. D h1 (u) By (6), the first gap g0 = h1 (u) contributes Z e·d g0

e·d g0 dD = g0 ln ≤ d, D g0

since x ln(e · d/x) is increasing for 0 < x ≤ d, and g0 ≤ d by (5). For r ≥ 1, a gap gr ≥ 2e · d contributes nothing to the integral, and a gap gr < 2e · d contributes at most Z e·d gr 2e · d dD = gr ln ≤ 2d, D gr gr /2 since x ln(c/x) ≤ c/e for every x > 0. There are k−2 such finite gaps, so the integral is at most d+2(k−2)d = ˆ v)] ≤ d + 2(2k − 3)d = (4k − 5)d. (2k − 3)d, and E[d(u, 23

e Proof of Theorem 5. The storage bound follows from Lemma 7, since the root labels add O(1) words to every entry of the first part. Every vertex on the walk computes the next port as in the general case of Section 4.2. By Lemma 15, the visit at level i(Dj ) succeeds once Dj ≥ d(u, v), so the message is always delivered. Besides id(v), the header contains the levels i1 , . . . , im , the index s of the current visit, and, as in Section 4.2, the e current tree identifier, target label, and return label, that is, O(1) words. The expected stretch follows from Lemma 17.

6.2

Deterministic ≈ 5.77k stretch

We now choose the sequence of visited levels deterministically.
4 Theorem 6. For every integer k ≥ 2, there is a 1 + 21/(k−1) ≈ 5.77k − 4.77 -stretch name-independent −1 e 1/k ) words and compact routing scheme with deterministic routing that uses average local storage of O(n e headers of O(1) words. We use the preprocessing, the visits, and the notation of Section 6.1. The cost of a sequence. Let σ = (i1 < · · · < im ) be a sequence of levels with i1 = 0 and im = k − 1, which the source visits in this order until a visit succeeds. For d > 0, let sσ (d) = min{s | gis > 2d} be the position of the first level of σ whose gap exceeds 2d. By Lemma 15, the visit at level isσ (d(u,v)) succeeds, so the costs of the visits give X ˆ v) ≤ d(u, v) + 2 d(u, his (u). (7) s≤sσ (d(u,v))

As in Section 4.3, the source knows every term of this bound except d(u, v). The deterministic choice.

Let

2 d d>0

X

β(σ) = sup

his (u)

s≤sσ (d)

be the largest extra stretch that (7) allows for σ, and let β ∗ = minσ β(σ). The source chooses a sequence attaining β ∗ and visits its levels as in Algorithm 2, without sampling X. The sum in β(σ) changes only when 2d crosses the gap of a level of σ, and between these values the bound decreases in d. So, as with Θ in Section 4.3, the source computes β(σ) from finitely many values of d. Stretch analysis.

By (7), the stretch is at most 1 + β ∗ , and the following bound suffices.

4 Lemma 18. β ∗ ≤ 21/(k−1) . −1

P Let λ = 1/(21/(k−1) − 1). If every prefix (i1 , . . . , it ) of σ with t ≥ 2 has s≤t his (u) ≤ λgit−1 , then β(σ) ≤ 4λ, since the sum in (7) includes hit (u) only if git−1 ≤ 2d(u, v). For the geometric gaps ga = 2a/(k−1) , every sequence has β(σ) ≥ 4λ, so the bound is tight. Proof. The proof is deferred to Section D. Proof of Theorem 6. By (7) and Lemma 18, the stretch is at most 1 + β ∗ ≤ 1 + 4/(21/(k−1) − 1), and 21/(k−1) − 1 ≥ ln 2/(k − 1). The storage and header bounds follow as in the proof of Theorem 5.

24

7

Name-independent routing with worst-case storage

e 1/k ) local storage at every vertex in In this section, we present our name-independent schemes with O(n unweighted graphs, and prove Theorems 7 and 8. We combine the search structures of Section 5.2 with the sequence of visits of Section 6. The source receives only id(v), so it knows neither pi (v) nor hi (v). It therefore uses its guesses of d(u, v) both to choose a pivot and to choose the radius of the search. Preprocessing. We use the preprocessing of Section 5.2, without labels. Every record in a search structure of a cluster tree T (C(w)) contains id(v) and L(v, T (C(w))). Routing.

If v ∈ C0 (u), route to v along a shortest path. Otherwise, the source starts with the lower bound    h1 (u) ≤ d(u, v). M = max 1, 2

Indeed, v ∈ / C0 (u) implies d(u, v) ≥ h1 (v), and hence h1 (u) ≤ d(u, v) + h1 (v) ≤ 2d(u, v). The source makes a sequence of visits, using increasing guesses D ≥ M . In a visit at level i, it first routes to pi (u) and requests a search with radius R = hi (u) + D. The pivot selects the smallest prefix tree Tj containing every cluster vertex at distance at most R. It checks the record locally if j = 0, and otherwise uses the search structure hosted on Tj−1 . By the minimality of j, the host tree has radius at most R. If the search succeeds, the message uses the retrieved label to reach v. Otherwise, it returns to u, which increases its guess and makes another visit. A failed search concerns only the searched prefix: it does not necessarily show that v is outside the whole cluster. The gain from visiting level i.

Write gi = hi+1 (u) − hi (u),

0 ≤ i < k,

where gk−1 = ∞. These gaps are known to the source. Suppose that d = d(u, v) ≤ D and gi > 2D. Then hi+1 (v) ≥ hi+1 (u) − d > hi (u) + d ≥ d(pi (u), v). Thus v ∈ C(pi (u)). Moreover, d(pi (u), v) ≤ hi (u) + D = R, so the searched prefix contains its record. The visit therefore succeeds. Hence, if gi > 2D, a failure proves d > D. For each guess, we choose i(D) = min{1 ≤ i < k : gi > 2D}. This level always exists because gk−1 = ∞. Since gi > 0, we have pi (u) ∈ Ai \ Ai+1 , so its cluster has at most S i+1 vertices. By Lemma 12 with radius at most R and ⌈logS N ⌉ ≤ i + 1, the walk to the record holder has length at most R + 2i. A failed visit costs at most 2hi (u) + 2R + 2i = 4hi (u) + 2D + 2i. On success, the search and subsequent delivery cost at most hi (u) + 2R + 2i + d(pi (u), v) ≤ d + 4hi (u) + 2D + 2i. We therefore write c(D) = 4hi(D) (u) + 2D + 2i(D). A failed visit costs at most c(D), and a successful visit costs at most d + c(D). Among the levels with gi > 2D, the first one minimizes this bound, since both hi (u) and i are nondecreasing. 25

7.1

Deterministic routing

Theorem 8. For every integer k ≥ 2, there is a 8(k−1) ln 2 + 9 ≈ 11.54k − 2.54 -stretch name-independent compact routing scheme for unweighted graphs with deterministic routing that uses worst-case local storage e 1/k ) words and headers of O(1) e of O(n words. As in the average-storage name-independent scheme, the source chooses a sequence that minimizes its largest extra-stretch bound. Let σ = (D1 < · · · < Dm ) be a sequence of integer guesses with D1 ≥ M and Dm = n − 1. The source visits i(D1 ), . . . , i(Dm ) until a search succeeds. For a possible distance d, let sσ (d) = min{s : Ds ≥ d}. The visit at position sσ (d) is guaranteed to succeed. Hence X ˆ v) ≤ d(u, v) + d(u,

c(Dr ).

r≤sσ (d(u,v))

The deterministic optimization is therefore ∗ βdet = min σ

1 d∈{M,...,n−1} d

X

max

c(Dr ).

r≤sσ (d)

∗ Every term is determined by the source’s own heights. A minimizing sequence gives stretch at most 1 + βdet .

Lemma 19. The deterministic optimization satisfies ∗ βdet ≤

8(k − 1) + 8. ln 2

Consequently, the deterministic routing scheme has stretch at most 8(k − 1) + 9. ln 2 Proof. The proof is deferred to Section E.

7.2

Randomized routing

Theorem 7. For every integer k ≥ 2, there is a (8k + 2e − 7, 2k − 2)-expected stretch name-independent e 1/k ) words and headers compact routing scheme for unweighted graphs that uses worst-case local storage of O(n e of O(1) words. We use randomly shifted geometric guesses, as in the average-storage name-independent scheme. The source samples X uniformly from [0, 1) and uses the guesses Dj of Lemma 20. At each guess, it visits i(Dj ) and performs the corresponding radius-limited search. It stops when a search succeeds. Lemma 20. Using the guesses Dj =

  1 j+X 1 M+ e − , 4 4

j = 0, 1, . . . ,

where X is uniform on [0, 1), the randomized routing scheme satisfies ˆ v)] ≤ (8k + 2e − 7)d(u, v) + 2k − 2. E[d(u, The expectation is over the source’s random shift, with the preprocessing fixed. 26

Proof. The proof is deferred to Section E. Proof of Theorems 7 and 8. The storage bound is as in Section 5.2. Besides id(v), the header contains the current guess, the selected level and search structure, and the current tree identifier, target label, and return e label, that is, O(1) words. The visit with the first guess D ≥ d(u, v) succeeds, so the message is always delivered. The stretch bounds are Lemmas 19 and 20.

8

Discussion

With average storage, randomized routing achieves the optimal expected stretch 2k − 1, while our deterministic stretch is ≈ 2.47k. The coefficient 1/ ln(3/2) of our deterministic scheme cannot be improved using only the inequalities of our analysis (Section B.4). e 1/k ) average Problem 1. Is there a labeled routing scheme with deterministic routing, stretch 2k −1, and O(n local storage? With worst-case storage, our bound is further from the lower bound. Our scheme has ( 38 k + 6, 49 k) ≈ (2.67k + 6, 0.44k)-expected stretch, and the lower bound is 2k − 1. e 1/k ) worst-case local Problem 2. Is there a labeled routing scheme with expected stretch 2k − 1 and O(n storage? For name-independent routing, our expected stretch 4k − 5 with average storage is the best bound that the distances of the source to its own pivots give, and the lower bound is 2k − 1 [AGM06a]. Closing this gap would require an analysis that uses more than the distances of the source to its pivots. Use of AI. ChatGPT and Claude were used to assist with drafting and revising the entire paper, checking mathematical arguments, verifying references and novelty, and solving the optimization problems in the appendices. The authors reviewed the suggestions and take full responsibility for the final content, including all results, proofs, and citations.

References [ABCP98] Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Near-linear time construction of sparse neighborhood covers. SIAM J. Comput., 28(1):263–277, 1998. [ABLP89] Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Compact distributed data structures for adaptive routing (extended abstract). In David S. Johnson, editor, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 479–489. ACM, 1989. [ABLP90] Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. J. Algorithms, 11(3):307–341, 1990. [ACL+ 06]

Marta Arias, Lenore J. Cowen, Kofi A. Laing, Rajmohan Rajaraman, and Orjeta Taka. Compact routing with name independence. SIAM J. Discret. Math., 20(3):705–726, 2006.

[ADD+ 93] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81–100, 1993. [AG11]

Ittai Abraham and Cyril Gavoille. On approximate distance labels and routing schemes with affine stretch. In David Peleg, editor, Distributed Computing - 25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011. Proceedings, volume 6950 of Lecture Notes in Computer Science, pages 404–415. Springer, 2011. 27

[AGGM06] Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. In 26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006, page 75. IEEE Computer Society, 2006. [AGH11]

Rachit Agarwal, Philip Brighten Godfrey, and Sariel Har-Peled. Approximate distance queries and compact routing in sparse graphs. In INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10-15 April 2011, Shanghai, China, pages 1754–1762. IEEE, 2011.

[AGH12]

Rachit Agarwal, Brighten Godfrey, and Sariel Har-Peled. Faster approximate distance queries and compact routing in sparse graphs. CoRR, abs/1201.2703, 2012.

[AGM04]

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Routing with improved communication-space trade-off. In Distributed Computing, 18th International Conference, DISC 2004, volume 3274 of Lecture Notes in Computer Science, pages 305–319. Springer, 2004.

[AGM05]

Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. Compact routing for graphs excluding a fixed minor. In Pierre Fraigniaud, editor, Distributed Computing, 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005, Proceedings, volume 3724 of Lecture Notes in Computer Science, pages 442–456. Springer, 2005.

[AGM06a] Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs: lower bounds. In Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2006, pages 207–216. ACM, 2006. [AGM06b] Ittai Abraham, Cyril Gavoille, and Dahlia Malkhi. On space-stretch trade-offs: upper bounds. In Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2006, pages 217–224. ACM, 2006. [AGM+ 08] Ittai Abraham, Cyril Gavoille, Dahlia Malkhi, Noam Nisan, and Mikkel Thorup. Compact name-independent routing with minimum stretch. ACM Trans. Algorithms, 4(3):37:1–37:12, 2008. [AKPW95] Noga Alon, Richard M. Karp, David Peleg, and Douglas B. West. A graph-theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78–100, 1995. [AM04]

Ittai Abraham and Dahlia Malkhi. Compact routing on euclidian metrics. In Soma Chaudhuri and Shay Kutten, editors, Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 141–149. ACM, 2004.

[AM05]

Ittai Abraham and Dahlia Malkhi. Name independent routing for growth bounded networks. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2005, pages 49–55. ACM, 2005.

[AP90]

Baruch Awerbuch and David Peleg. Sparse partitions. In 31st Annual Symposium on Foundations of Computer Science, FOCS 1990, pages 503–513. IEEE Computer Society, 1990.

[AP92]

Baruch Awerbuch and David Peleg. Routing with polynomial communication-space trade-off. SIAM J. Discret. Math., 5(2):151–162, 1992.

[Bar96]

Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, pages 184–193. IEEE Computer Society, 1996.

[BS07]

Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532–563, 2007. 28

[CDG20]

Ruoxu Cen, Ran Duan, and Yong Gu. Roundtrip spanners with (2k-1) stretch. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 24:1–24:11. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[CGMZ16] T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. ACM Trans. Algorithms, 12(4), 2016. [Che13a]

Shiri Chechik. Compact routing schemes with improved stretch. In Panagiota Fatourou and Gadi Taubenfeld, editors, ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22-24, 2013, pages 33–41. ACM, 2013.

[Che13b]

Shiri Chechik. Fault-tolerant compact routing schemes for general graphs. Inf. Comput., 222:36– 44, 2013.

[Che14]

Shiri Chechik. Approximate distance oracles with constant query time. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 654–663. ACM, 2014.

[Che15]

Shiri Chechik. Approximate distance oracles with improved bounds. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 1–10. ACM, 2015.

[CI03]

Tiziana Calamoneri and Miriam Di Ianni. Interval routing & layered cross product: compact routing schemes for butterflies, meshes of trees, fat trees and benes networks. J. Parallel Distributed Comput., 63(11):1017–1025, 2003.

[CKNY08] Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young. Incremental medians via online bidding. Algorithmica, 50(4):455–478, 2008. [CLPR12] Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. Algorithmica, 63(4):861–882, 2012. [Cow01]

Lenore Cowen. Compact routing with minimum stretch. J. Algorithms, 38(1):170–183, 2001.

[CW04]

Lenore Cowen and Christopher G. Wagner. Compact roundtrip routing in directed networks. J. Algorithms, 50(1):79–95, 2004.

[CZ24]

Shiri Chechik and Tianyi Zhang. Path-reporting distance oracles with logarithmic stretch and linear size. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 of LIPIcs, pages 42:1–42:18. Schloss Dagstuhl - LeibnizZentrum für Informatik, 2024.

[DG02]

Yon Dourisboure and Cyril Gavoille. Improved compact routing scheme for chordal graphs. In Dahlia Malkhi, editor, Distributed Computing, 16th International Conference, DISC 2002, Toulouse, France, October 28-30, 2002 Proceedings, volume 2508 of Lecture Notes in Computer Science, pages 252–264. Springer, 2002.

[DL07]

Feodor F. Dragan and Irina Lomonosov. On compact and efficient routing in certain graph classes. Discret. Appl. Math., 155(11):1458–1470, 2007.

[DP26]

Michal Dory and Merav Parter. Fault-tolerant labeling and compact routing schemes. SIAM J. Comput., 55(4):671–707, 2026.

29

[DSDP15] Atish Das Sarma, Michael Dinitz, and Gopal Pandurangan. Efficient distributed computation of distance sketches in networks. Distributed Computing, 28(5):309–320, 2015. [EFN18]

Michael Elkin, Arnold Filtser, and Ofer Neiman. Prioritized metric structures and embedding. SIAM Journal on Computing, 47(3):829–858, 2018.

[EGP03]

Tamar Eilam, Cyril Gavoille, and David Peleg. Compact routing schemes with low stretch factor. J. Algorithms, 46(2):97–114, 2003.

[EGP07]

Tamar Eilam, Cyril Gavoille, and David Peleg. Average stretch analysis of compact routing schemes. Discret. Appl. Math., 155(5):598–610, 2007.

[Elk08]

Michael Elkin. Sparse graph spanners. In Ming-Yang Kao, editor, Encyclopedia of Algorithms 2008 Edition. Springer, 2008.

[EN18a]

Michael Elkin and Ofer Neiman. Near-optimal distributed routing with low memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pages 207–216. ACM, 2018.

[EN18b]

Michael Elkin and Ofer Neiman. On efficient distributed construction of near optimal routing schemes. Distributed Comput., 31(2):119–137, 2018.

[ENW16]

Michael Elkin, Ofer Neiman, and Christian Wulff-Nilsen. Space-efficient path-reporting approximate distance oracles. Theor. Comput. Sci., 651:1–10, 2016.

[EP16]

Michael Elkin and Seth Pettie. A linear-size logarithmic stretch path-reporting distance oracle for general graphs. ACM Trans. Algorithms, 12(4):50:1–50:31, 2016.

[Erd64]

Paul Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29–36. Publ. House Czechoslovak Acad. Sci., Prague, 1964.

[ES26]

Michael Elkin and Idan Shabat. Path-reporting distance oracles with logarithmic stretch and size O(n log log n). SIAM J. Comput., 55(6):1229–1292, 2026.

[FG01]

Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, volume 2076 of Lecture Notes in Computer Science, pages 757–772. Springer, 2001.

[FG02]

Pierre Fraigniaud and Cyril Gavoille. A space lower bound for routing in trees. In Helmut Alt and Afonso Ferreira, editors, STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes - Juan les Pins, France, March 14-16, 2002, Proceedings, volume 2285 of Lecture Notes in Computer Science, pages 65–75. Springer, 2002.

[FRT04]

Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485–497, 2004.

[Gav00]

Cyril Gavoille. A survey on interval routing. Theor. Comput. Sci., 245(2):217–253, 2000.

[Gav01]

Cyril Gavoille. Routing in distributed networks: overview and open problems. SIGACT News, 32(1):36–52, 2001.

[GG01]

Cyril Gavoille and Marc Gengler. Space-efficiency for routing schemes of stretch factor three. J. Parallel Distributed Comput., 61(5):679–687, 2001.

[GGHI13]

Cyril Gavoille, Christian Glacet, Nicolas Hanusse, and David Ilcinkas. On the communication complexity of distributed name-independent routing schemes. In Yehuda Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings, volume 8205 of Lecture Notes in Computer Science, pages 418–432. Springer, 2013. 30

[GH99]

Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Jirı́ Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages and Programming, 26th International Colloquium, ICALP’99, Prague, Czech Republic, July 11-15, 1999, Proceedings, volume 1644 of Lecture Notes in Computer Science, pages 351–360. Springer, 1999.

[GKK+ 01] Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. In Proceedings of the 9th Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science, pages 476–487, 2001. [GP96]

Cyril Gavoille and Stephane Perennes. Memory requirements for routing in distributed networks (extended abstract). In James E. Burns and Yoram Moses, editors, Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, May 23-26, 1996, pages 125–133. ACM, 1996.

[GP03]

Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed Comput., 16(2-3):111–120, 2003.

[GPPR04] Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85–112, 2004. [HJWX24] Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams, and Zixuan Xu. Improved roundtrip spanners, emulators, and directed girth approximation. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4641–4669. SIAM, 2024. [HP01]

Yehuda Hassin and David Peleg. Sparse communication networks and efficient routing in the plane. Distributed Comput., 14(4):205–215, 2001.

[IO02]

Kazuo Iwama and Masaki Okita. Compact routing for average-case networks. In Aleta Ricciardi, editor, Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21-24, 2002, page 255. ACM, 2002.

[IO03]

Kazuo Iwama and Masaki Okita. Compact routing for flat networks. In Faith Ellen Fich, editor, Distributed Computing, 17th International Conference, DISC 2003, Sorrento, Italy, October 1-3, 2003, Proceedings, volume 2848 of Lecture Notes in Computer Science, pages 196–210. Springer, 2003.

[KFY04]

Dmitri V. Krioukov, Kevin R. Fall, and Xiaowei Yang. Compact routing on internet-like graphs. In Proceedings IEEE INFOCOM 2004, The 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, March 7-11, 2004. IEEE, 2004.

[KK77]

Leonard Kleinrock and Farouk Kamoun. Hierarchical routing for large networks: Performance evaluation and optimization. Computer Networks, 1(3):155–174, 1977.

[KR25a]

Avi Kadria and Liam Roditty. Compact routing schemes in undirected and directed graphs. In 39th International Symposium on Distributed Computing, DISC 2025, volume 356 of LIPIcs, pages 38:1–38:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.

[KR25b]

Avi Kadria and Liam Roditty. New approximate distance oracles and their applications. In Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC), volume 359 of LIPIcs, pages 43:1–43:17, 2025.

[KR26a]

Avi Kadria and Liam Roditty. Faster algorithms for (2k − 1)-stretch distance oracles. In 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, volume 374 of LIPIcs, pages 121:1–121:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. 31

[KR26b]

Avi Kadria and Liam Roditty. Tight space bounds for pivot-based distance oracles in sparse graphs. arXiv preprint arXiv:2610.29624, 2026.

[KRT96]

Ming-Yang Kao, John H. Reif, and Stephen R. Tate. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput., 131(1):63–79, 1996.

[KRX06]

Goran Konjevod, Andréa W. Richa, and Donglin Xia. Optimal-stretch name-independent compact routing in doubling metrics. In Eric Ruppert and Dahlia Malkhi, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006, pages 198–207. ACM, 2006.

[KRX16]

Goran Konjevod, Andréa W. Richa, and Donglin Xia. Scale-free compact routing schemes in networks of low doubling dimension. ACM Trans. Algorithms, 12(3), 2016.

[KRXY07] Goran Konjevod, Andréa W. Richa, Donglin Xia, and Hai Yu. Compact routing with slack in low doubling dimension. In Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, PODC 2007, pages 71–80. ACM, 2007. [Lai07]

Kofi A. Laing. Name-independent compact routing in trees. Inf. Process. Lett., 103(2):57–60, 2007.

[LP13]

Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages. In Symposium on Theory of Computing Conference, STOC 2013, pages 381–390. ACM, 2013.

[LPP19]

Christoph Lenzen, Boaz Patt-Shamir, and David Peleg. Distributed distance computation and routing with small messages. Distributed Comput., 32(2):133–157, 2019.

[LR07]

Kofi A. Laing and Rajmohan Rajaraman. A space lower bound for name-independent compact routing in trees. J. Interconnect. Networks, 8(3):229–251, 2007.

[Lu10]

Hsueh-I Lu. Improved compact routing tables for planar networks via orderly spanning trees. SIAM J. Discret. Math., 23(4):2079–2092, 2010.

[MN07]

Manor Mendel and Assaf Naor. Ramsey partitions and proximity data structures. J. Eur. Math. Soc., 9(2):253–275, 2007.

[MW20]

Wolfgang Mulzer and Max Willert. Compact routing in unit disk graphs. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 16:1–16:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.

[NO99]

Lata Narayanan and Jaroslav Opatrny. Compact routing on chordal rings of degree 4. Algorithmica, 23(1):72–96, 1999.

[NS24]

Ofer Neiman and Idan Shabat. Path-reporting distance oracles with linear size. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of Leibniz International Proceedings in Informatics, pages 36:1–36:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.

[Pel00a]

David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications. SIAM, 2000.

[Pel00b]

David Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33(3):167–176, 2000.

[PR14]

Mihai Pǎtraşcu and Liam Roditty. Distance oracles beyond the thorup-zwick bound. SIAM J. Comput., 43(1):300–311, 2014.

32

[PRS+ 18]

Jakub Pachocki, Liam Roditty, Aaron Sidford, Roei Tov, and Virginia Vassilevska Williams. Approximating cycles in directed graphs: Fast algorithms for girth and roundtrip spanners. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1374– 1392. SIAM, 2018.

[PRT12]

Mihai Pǎtraşcu, Liam Roditty, and Mikkel Thorup. A new infinity of distance oracles for sparse graphs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 738–747. IEEE Computer Society, 2012.

[PU89]

David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. J. ACM, 36(3):510–530, 1989.

[Räc02]

Harald Räcke. Minimizing congestion in general networks. In 43rd Symposium on Foundations of Computer Science, FOCS 2002, pages 43–52. IEEE Computer Society, 2002.

[Rod16]

Liam Roditty. Distance oracles for sparse graphs. In Encyclopedia of Algorithms, pages 563–564. Springer, 2016.

[RT15]

Liam Roditty and Roei Tov. New routing techniques and their applications. In Chryssis Georgiou and Paul G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21 - 23, 2015, pages 23–32. ACM, 2015.

[RT16]

Liam Roditty and Roei Tov. Close to linear space routing schemes. Distributed Comput., 29(1):65–74, 2016.

[RT23]

Liam Roditty and Roei Tov. Approximate distance oracles with improved stretch for sparse graphs. Theoretical Computer Science, 943:89–101, 2023.

[RTZ05]

Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In Luı́s Caires, Giuseppe F. Italiano, Luı́s Monteiro, Catuscia Palamidessi, and Moti Yung, editors, Automata, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 261–272. Springer, 2005.

[RTZ08]

Liam Roditty, Mikkel Thorup, and Uri Zwick. Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms, 4(3):29:1–29:17, 2008.

[SK85]

Nicola Santoro and Ramez Khatib. Labelling and implicit routing in networks. Comput. J., 28(1):5–8, 1985.

[Sli07]

Aleksandrs Slivkins. Distance estimation and object location via rings of neighbors. Distributed Comput., 19(4):313–333, 2007.

[Som14]

Christian Sommer. Shortest-path queries in static networks. 46(4):45:1–45:31, 2014.

[SVY09]

Christian Sommer, Elad Verbin, and Wei Yu. Distance oracles for sparse graphs. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 703–712. IEEE Computer Society, 2009.

[SZ23]

Eli Stafford and Chunjiang Zhu. Improved sourcewise roundtrip spanners with constant stretch. In Weili Wu and Guangmo Tong, editors, Computing and Combinatorics - 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15-17, 2023, Proceedings, Part I, volume 14422 of Lecture Notes in Computer Science, pages 297–309. Springer, 2023.

33

ACM Computing Surveys,

[Tal04]

Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, STOC 2004, pages 281–290. ACM, 2004.

[Tho04]

Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. Journal of the ACM (JACM), 51(6):993–1024, 2004.

[TYZ09]

Mingdong Tang, Jing Yang, and Guoqing Zhang. Compact routing on random power law graphs. In Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing, DASC 2009, Chengdu, China, 12-14 December, 2009, pages 575–578. IEEE Computer Society, 2009.

[TZ01]

Mikkel Thorup and Uri Zwick. Compact routing schemes. In Arnold L. Rosenberg, editor, Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4-6, 2001, pages 1–10. ACM, 2001.

[TZ05]

Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

[VB81]

Leslie G. Valiant and Gordon J. Brebner. Universal schemes for parallel communication. In Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981, pages 263–277. ACM, 1981.

[vLT87]

Jan van Leeuwen and Richard B. Tan. Interval routing. Comput. J., 30(4):298–307, 1987.

[Wul12]

Christian Wulff-Nilsen. Approximate distance oracles with improved preprocessing time. In Yuval Rabani, editor, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 202–208. SIAM, 2012.

[Wul13]

Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 539–549. SIAM, 2013.

[ZHL21]

Chun Jiang Zhu, Song Han, and Kam-Yiu Lam. A fast algorithm for source-wise round-trip spanners. Theoretical Computer Science, 876:34–44, 2021.

[Zin22]

Anatoliy Zinovyev. Space-stretch tradeoff in routing revisited. In 36th International Symposium on Distributed Computing, DISC 2022, volume 246 of LIPIcs, pages 37:1–37:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.

[ZL17]

Chun Jiang Zhu and Kam-Yiu Lam. Source-wise round-trip spanners. Information Processing Letters, 124:42–45, 2017.

[ZL18]

Chun Jiang Zhu and Kam-Yiu Lam. Deterministic improved round-trip spanners. Information Processing Letters, 129:57–60, 2018.

A

Summary of our results

Table 3 lists the stretch of our schemes in all four models, for unweighted and weighted graphs.

34

Stretch 2k − 1 ≈ 2.47k − 1.47 4k − 5 ≈ 5.77k − 4.77 (≈ 2.67k + 6, ≈ 0.44k) ≈ 3.05k + 1 (≈ 8k − 1.56, 2k − 2) ≈ 11.54k − 2.54 ≈ (1 + ε)3.07k + O(1) ≈ (1 + ε)3.42k + O(1) ≈ 14.62(1 + ε)2 k + O(1) 25.6(1 + ε)2 k + O(1)

Model labeled labeled name-independent name-independent labeled labeled name-independent name-independent labeled labeled name-independent name-independent

Storage e 1/k ) average O(n e 1/k ) average O(n e 1/k ) average O(n e 1/k ) average O(n e 1/k ) worst-case O(n e 1/k ) worst-case O(n e 1/k ) worst-case O(n e 1/k ) worst-case O(n e −1 n1/k log ∆) worst-case O(ε e −1 n1/k log ∆) worst-case O(ε e −1 n1/k log ∆) worst-case O(ε e −1 n1/k log ∆) worst-case O(ε

Graphs weighted weighted weighted weighted unweighted unweighted unweighted unweighted weighted weighted weighted weighted

Reference Theorem 1⋆ Theorem 2 Theorem 5⋆ Theorem 6 Theorem 3⋆ Theorem 4 Theorem 7⋆ Theorem 8 Theorem 10⋆ Theorem 9 Theorem 12⋆ Theorem 11

Table 3: Our routing schemes in all four models, where ∆ is the aspect ratio of the graph and 0 < ε < 1. ˆ v) ≤ α d(u, v) + β, or E[d(u, ˆ v)] ≤ α d(u, v) + β for rows A pair (α, β) denotes (α, β)-stretch, that is, d(u, marked ⋆ . ⋆ Expected stretch.

B

Proofs of the optimization bounds

This appendix proves Lemma 10 in Section B.1 and Lemma 11 in Section B.2. Section B.3 compares the deterministic bound with the previous bound of Kadria and Roditty [KR25a]. Section B.4 shows that the coefficient 1/ ln(3/2) in Lemma 11 cannot be improved using only the inequalities of Lemma 21. Fix u, v, τ , and M as in Section 4.3. In this appendix, we divide all distances by M . Write xi =

hi (u) , M

yi =

hi (v) M

(0 ≤ i ≤ τ ),

H = yτ ,

and δi = yi+1 − xi for i ∈ [τ ]. So δi is the threshold of level i, divided by M . Lemma 21. The normalized heights are nondecreasing, x0 = y0 = 0, 0 < H ≤ 2τ − 1, and x1 ≤ 1 and y1 ≤ 1,

(N1)

xi+1 ≤ yi + 1

(0 ≤ i < τ ),

(N2)

|xi − yi | ≤ 1

(0 ≤ i ≤ τ ),

(N3)

0 ≤ yi+1 − yi ≤ 2

(0 ≤ i < τ ).

(N4)

Proof. The bound on H follows from (1). The definition of M gives (N1)–(N3), and monotonicity together with yi+1 ≤ xi+1 + 1 ≤ yi + 2 gives (N4). Penalties. Let d = θM be a possible value of d(u, v), so θ ≥ 1, and let i ∈ [τ ]. Dividing (2) by d shows ˆ v) − d)/d of level i is at most its penalty that the extra stretch (d(u, χi (θ) =

2xi + 2H · 1[θ ≥ δi ] θ

(θ ≥ 1).

Since χi is decreasing on [1, δi ) and on [max{1, δi }, ∞), the quantity βi of Section 4.5 is the largest penalty of level i:   2(xi + H) βi = max 2xi , = sup χi (θ). max{1, δi } θ≥1 Since x0 = 0 and δ0 = y1 ≤ 1 by (N1), β0 = 2H. After substituting d = θM and dividing the constraints by d, we can write (3) as X z ∗ = min max πi χi (θ), (8) π∈P([τ ]) θ∈Θ/M

35

i∈[τ ]

where Θ/M = {d/M : d ∈ Θ} = {1} ∪ {δi : i ∈ [τ ], δi > 1}.

B.1

The randomized bound

By LP duality, it suffices to show that for every distribution of the normalized distance θ, some level has expected penalty at most 2τ . Reweighting the distribution by 1/θ turns the expected penalty of a level into its expected extra cost divided by the mean m of the reweighted distribution. Every level whose visit, on success, costs less than the smallest expected extra cost must fail with large probability. So its threshold is at most a quantile of the distribution. By (N2), xi+2 − xi is then at most 1 plus this quantile. As xi grows, the required failure probability decreases, so different levels use different parts of the distribution. Measured in units of these quantiles, the height grows by at most 1 per level. The Cauchy–Schwarz inequality turns this into a bound in terms of m. Quantiles. For a distribution ν on a finite subset of [1, ∞), let m = Eθ∼ν [θ] and F̄ (ζ) = Prθ∼ν [θ ≥ ζ]. Its quantile function is f (α) = min{ζ ∈ supp(ν) | Prθ∼ν [θ ≤ ζ] > α} for 0 ≤ α < 1. It is nondecreasing, f ≥ 1, R1 and m = 0 f (α) dα. Moreover, F̄ (ζ) ≥ 1 − α =⇒ ζ ≤ f (α)

(0 ≤ α < 1).

(9)

Indeed, if f (α) < ζ, then Prθ∼ν [θ ≤ f (α)] ≤ 1 − F̄ (ζ) ≤ α, contradicting the definition of f (α). For such ν, let
C = min 2xi + 2H F̄ (δi ) . i∈[τ ]

Lemma 10. z ∗ ≤ 2τ . Proof. LP duality, applied to (8), gives z∗ =

max

min

λ∈P(Θ/M ) i∈[τ ]

X

λ(θ)χi (θ).

(10)

θ∈Θ/M

P Fix λ, let Z = θ∈Θ/M λ(θ)/θ > 0, and set ν(θ) = λ(θ)/(θZ). Then ν is a distribution with mean m = 1/Z. Since λ(θ) = θν(θ)/m, every level i has X

λ(θ)χi (θ) =

θ∈Θ/M

2xi + 2H F̄ (δi ) Eθ∼ν [θχi (θ)] = . m m

Hence the minimum over i is C/m, which is at most 2τ by Lemma 22 below. Since this holds for every λ, (10) proves z ∗ ≤ 2τ . Lemma 22. For every distribution ν on a finite subset of [1, ∞) with mean m, mini∈[τ ] 2xi + 2H Prθ∼ν [θ ≥
δi ] ≤ 2τ m. Proof. If C ≤ 2τ , the lemma holds since m ≥ 1. Otherwise, F̄ (δ0 ) = 1 since δ0 ≤ 1, so 2τ < C ≤ 2H ≤ 2(2τ − 1) by Lemma 21. Let r = C/(2H) ∈ (1/2, 1] and αi = 1 − r + xi /H. For every i ∈ [τ ] with xi < rH, the definition of C gives F̄ (δi ) ≥ r − xi /H = 1 − αi , so (9) gives δi ≤ f (αi ).

(11)

Let

Z min{z,rH} φ(w) = 1 − r + rf (1 − r + w/H)

(0 ≤ w < rH),

Ψ(z) = 0

Since f is nondecreasing and f ≥ 1, φ is nondecreasing and φ ≥ 1.

36

dw φ(w)

(z ≥ 0).

Claim 22.1. Ψ(xj ) ≤ j

(0 ≤ j < τ ).

Proof. Since φ ≥ 1, we have Ψ(z) ≤ z, so Ψ(x0 ) = 0 and Ψ(x1 ) ≤ 1 by (N1). Let 0 ≤ i ≤ τ − 3. Since Ψ is constant on [rH, ∞), we may assume xi < rH. By (N2) and (11), xi+2 − xi ≤ 1 + δi ≤ 1 + f (αi ) ≤ 2φ(xi ), where the last inequality uses r ≥ 1/2 and f ≥ 1. Since φ ≥ φ(xi ) on [xi , rH), we get Ψ(xi+2 ) − Ψ(xi ) ≤ 2, and induction proves the claim. Claim 22.2. Ψ(rH) ≤ τ . Proof. By Claim 22.1, it suffices to show Ψ(rH) − Ψ(xτ −1 ) ≤ 1, and we may assume xτ −1 < rH. Since δτ −1 = H − xτ −1 , (11) gives rH − xτ −1 ≤ rδτ −1 ≤ rf (ατ −1 ) ≤ φ(xτ −1 ). Hence Ψ(rH) − Ψ(xτ −1 ) ≤ (rH − xτ −1 )/φ(xτ −1 ) ≤ 1. Substituting α = 1 − r + w/H and using f ≥ 1 on [0, 1 − r), we get Z rH

Z 1   φ(w) dw = rH 1 − r + f (α) dα ≤ rHm.

0

1−r

By the Cauchy–Schwarz inequality and Claim 22.2, (rH)2 ≤ Ψ(rH)

Z rH φ(w) dw ≤ τ rHm. 0

Hence C = 2rH ≤ 2τ m.

B.2

The deterministic bound

If τ = 1, then β ∗ ≤ β0 = 2H ≤ 2 < 1/ ln(3/2). Otherwise, write τ = 2q + s, with q ≥ 1 and s ∈ {0, 1}. Let tτ > 0 solve  3tτ + 1 1 q = . (12) 1+ tτ 2tτ + s + 1 The left side decreases from ∞ to 1, and the right side increases to 3/2, so increasing the √ q or s increases √ solution. For τ = 2, the equation reads 1+1/t = (3t+1)/(2t+1), whose solution is 1+ 2. Hence tτ ≥ 1+
2. Going from (q, 1) to (q + 1, 0) multiplies the left side of (2t + s + 1)ρq = 3t + 1 by (2t + 1)(t + 1)/ t(2t + 2) = (2t + 1)/(2t) ≥ 1, so tτ is nondecreasing in τ . Let ρ = 1 + 1/tτ . We show β ∗ ≤ 2tτ and then 2tτ < τ / ln(3/2). Lemma 23. β ∗ ≤ 2tτ . Proof. Let t = tτ , and suppose that β ∗ > 2t. Then H > t, since β0 = 2H. A level i + 1 with xi+1 ≤ t must have δi+1 < (xi+1 + H)/t, since otherwise βi+1 ≤ 2t. Since xi+1 ≤ yi + 1 by (N2), this bounds yi+2 in terms of yi while yi ≤ t − 1. After that, y grows by at most 2 per level by (N4). Together, these bounds contradict H > t. Equation (12) gives (2t + s + 1)ρq = 3t + 1 and ρq < 3/2. Subtracting tρq + t + 1 from both sides of the first identity gives (2 − ρq )t = s + (t + s + 1)(ρq − 1). (13)

37

Growth over pairs of levels. If 0 ≤ i ≤ τ − 2 and yi ≤ t − 1, then xi+1 ≤ yi + 1 ≤ t by (N2). Since 2xi+1 ≤ 2t < βi+1 , the second term of βi+1 exceeds 2t. Hence δi+1 ≤ max{1, δi+1 } < (xi+1 + H)/t, and yi+2 = xi+1 + δi+1 < ρ(yi + 1) + H/t. Equivalently, yi+2 + H + t + 1 < ρ(yi + H + t + 1).

(14)

Following the recurrence. Since ys ≤ s ≤ 1 < t − 1 by (N1) and ys+2q = H > t, there is a first j ∗ ∈ {1, . . . , q} with ys+2j ∗ > t − 1. Let y ∗ = ys+2j ∗ . Applying (14) for i = s, s + 2, . . . , s + 2j ∗ − 2, starting from ys ≤ s, gives ∗ y ∗ < s + (H + t + s + 1)(ρj − 1). (15) Let a = q − j ∗ be the number of remaining pairs. By (N4), H ≤ y ∗ + 4a. If a = 0, then y ∗ = H, so (15) and (13) give (2 − ρq )H < s + (t + s + 1)(ρq − 1) = (2 − ρq )t, contradicting H > t. ∗ If a ≥ 1, we substitute H ≤ y ∗ + 4a into (15) and use y ∗ > t − 1. Since 2 − ρj > 0, this yields ∗

∗

(2 − ρj )(t − 1) < s + (4a + t + s + 1)(ρj − 1). ∗

Rearranging gives 3t − 1 + 4a < (2t + s + 4a)ρj , and multiplying by ρa , with j ∗ + a = q, gives (3t − 1 + 4a)ρa < (2t + s + 4a)ρq .

(16)

But Bernoulli’s inequality bounds the left side from below by (3t − 1 + 4a)(1 + a/t) = 3t − 1 + 7a +

(4a − 1)a ≥ 3t − 1 + 7a, t

whereas (2t + s + 1)ρq = 3t + 1 and ρq < 3/2 bound the right side by (2t + s + 4a)ρq = 3t + 1 + (4a − 1)ρq < 3t + 6a − 12 . These bounds contradict (16), since a ≥ 1. It remains to compare 2tτ with τ / ln(3/2). Lemma 11. β ∗ ≤ τ / ln(3/2). √ Proof. By Lemma √ 23 and 2tτ = 2/(ρ − 1), it suffices to show that τ (ρ − 1)/2 > ln(3/2). Here 1 < ρ ≤ 2, since tτ ≥ 1 + 2. We use the standard bounds 2(ω − 1) 1 1 ≤ ln ω ≤ ω− (ω ≥ 1). (17) ω+1 2 ω √ Substituting tτ = 1/(ρ − 1) into (12) gives ρτ /2 = (ρ + 2)/(ρ + 1) when s = 0, and ρτ /2 = (ρ + 2)/(2 ρ) √ when s = 1. Since 2 ρ ≤ ρ + 1, both imply ρτ /2 ≥ (ρ + 2)/(ρ + 1). The upper bound in (17), applied to √ ρ, now gives τ (ρ − 1) √ τ ρ+2 √ ≥ ρ ln ρ ≥ ρ ln . 2 2 ρ+1 √ √ Let η(ξ) = ξ ln((ξ + 2)/(ξ + 1)) for 1 ≤ ξ ≤ 2. The lower bound in (17) gives   1 ξ+2 2ξ 2 − ξ2 η ′ (ξ) = √ ln − ≥√ . ξ + 1 (ξ + 1)(ξ + 2) 2 ξ ξ(2ξ + 3)(ξ + 1)(ξ + 2) √ Thus η is strictly increasing on [1, 2], so η(ρ) > η(1) = ln(3/2). 38

B.3

Comparison with the previous bound

For k ≥ 3, we compare Theorem 2 with Corollary 4.1 of Kadria and Roditty [KR25a]. Asymptotically, their 1 k + O(1) ≈ 2.47k. We show that ours is smaller for every bound is at least 52 k − O(1), while ours is ln(3/2) ′ k ≥ 3. Write k − 1 = 2ℓ + s , with ℓ ≥ 1 and s′ ∈ {0, 1}. Their scheme visits p2i (u) only if the threshold h2i+1 (v)−h2i (u) exceeds ci times its current lower bound on d(u, v). Their Corollary 4.1 is the case τ = k −1, where the constants are ℓ−i P c0 = 1, ci = 2 − (1 ≤ i ≤ ℓ). ℓ + j<i cj Pℓ Pℓ It bounds the stretch by 2 i=0 ci + 2ℓ + 1 for k = 2ℓ + 2, and by 2 i=0 ci + 2ℓ − 1 for k = 2ℓ + 1. In both Pℓ Pℓ−1 cases, the bound is 2ℓP − 1 + 2s′ + 2 i=0 ci , and since cℓ = 2, this is 2ℓ + 3 + 2s′ + 2 i=0 ci . By induction, ci ≥ 1 for every i, so j<i cj ≥ i. Therefore ci ≥ 2 − Summing gives

ℓ−i 2i i =1+ ≥1+ ℓ+i ℓ+i ℓ

(0 ≤ i < ℓ).

P

i<ℓ ci ≥ (3ℓ − 1)/2, so their bound is at least

5ℓ + 2 + 2s′ > 1 + 52 (k − 1), since 25 (k − 1) = 5ℓ + 52 s′ and s′ ≤ 1. Our bound is at most 1 + (k − 1)/ ln(3/2) < 1 + 52 (k − 1), since ln(3/2) > 2/5. Thus our stretch bound is strictly smaller for every k ≥ 3.

B.4

A tight profile for the deterministic bound

We give normalized heights for which every level has βi = 2tτ . These heights satisfy (N1)–(N4) but need not come from a graph. Hence Lemma 23 cannot be improved using only these inequalities. Write t = tτ . Set x0 = y0 = 0, y1 = 1, and xi = yi−1 + 1

(1 ≤ i ≤ τ ),

yi+1 = xi + 1 +

xi t

(1 ≤ i < τ ).

The heights. The two rules give yi+1 = ρ(yi−1 + 1) + 1, that is, yi+1 + 2t + 1 = ρ(yi−1 + 2t + 1). Starting from y0 = 0 and y1 = 1, we get y2j = (2t + 1)(ρj − 1),

y2j+1 = (2t + 2)ρj − (2t + 1).

The equation yτ = t reads (2t + s + 1)ρq = 3t + 1, which is (12). Hence H = yτ = t. The increments of y are 1, ρ, ρ, ρ2 , ρ2 , . . ., ending with ρq . Since ρq < 3/2 by (12), they lie in [1, 3/2). Since xi = yi−1 + 1, we have yi − xi = (yi − yi−1 ) − 1 ∈ [0, 1/2) for i ≥ 1. Hence both sequences are nondecreasing, and (N1)–(N4) hold, with equality in (N2). Also H < 1 + 32 (τ − 1) ≤ 2τ − 1. The penalties.

For 1 ≤ i < τ , the second rule gives δi = yi+1 − xi = 1 + xi /t > 1, and xi ≤ yi ≤ t. Hence   2(xi + t) βi = max 2xi , = 2t = β0 , 1 + xi /t

so β ∗ = 2tτ . Asymptotics. in (12) gives

Since every increment is at least 1, we have t = H ≥ τ , so q = O(t). Taking logarithms

1  1 1 3t + 1 3 q +O = q ln 1 + = ln = ln + O . t t t 2t + s + 1 2 t Thus tτ = q/ ln(3/2) + O(1), so 2tτ = τ / ln(3/2) + O(1), and the coefficient 1/ ln(3/2) in Lemma 11 cannot be improved using only the inequalities of Lemma 21. 39

C

Proofs of the worst-case optimization bounds

This appendix proves Lemma 13 in Section C.1 and Lemma 14 in Section C.2. We use the notation of Sections 5.3 and 5.4.

C.1

The deterministic bound

Lemma 13. Let

8

cM =

3M X

1 + (4 + 1/M )

r=2M +1

Then β ∗ ≤ cM τ + 2 +

cM (M − 1) , 4M + 2

cM ≤

. 1 r 8 . 1 + 4 ln(3/2)

Proof. Recall that the heights are nondecreasing integers and satisfy h1 (u), h1 (v) ≤ M,

hi+1 (u) ≤ hi (v) + M,

|hi (u) − hi (v)| ≤ M.

Consequently, H ≤ (2τ − 1)M,

δi ≤ 3M,

hi+2 (u) − hi (u) ≤ M + δi

(0 ≤ i ≤ τ − 2).

Suppose that the first claimed bound is false, and choose cM τ + 2 +

cM (M − 1) < β < β∗. 4M + 2

P3M Since β < β ∗ ≤ 2H/M , we have 2H > βM . Also cM > 2, since (4 + 1/M ) r=2M +1 1/r < 5/2 < 3, so β > 2τ + 2. Set zi = hi (u) + i/2 (0 ≤ i ≤ τ ), zτ +1 = H + M + (τ + 1)/2. The height inequalities give zi+2 − zi ≤ M + 1 + δi

(0 ≤ i < τ ).

For i = τ − 1, this follows directly from the definition of zτ +1 . We first bound δi while zi is small. Let b=

M (β − 2) − H + 1 > 0. 2

If 1 ≤ i < τ and zi < b, define 

 4zi + 2H − 2 + 1. t= β−2 The inequalities 2H > βM and zi < b imply M < t ≤ 2M . Indeed, 4zi + 2H − 2 ≥ M (β − 2) since 2H − 2 > βM − 2 ≥ M (β − 2), so t > M . And zi < b means 4zi + 2H − 2 < 2M (β − 2), so t ≤ 2M . If δi ≥ t, this is an available distance guess. Moreover, 4zi + 2t − 2 + 2H < βt and, since t ≤ 2M and 2H > βM , 4zi + 2t − 2 < βt − 2H < βM.

40

Hence both terms of the maximum in the definition of β ∗ for the pair (i, t) are less than β (the first term by 4zi + 2t − 2 < βM , the second by 4zi + 2t − 2 + 2H < βt), so β ∗ < β, contradicting β < β ∗ . Hence   4zi + 2H − 2 δi ≤ whenever zi < b. β−2 This inequality also holds for i = 0, because δ0 = h1 (v) ≤ M . Define  M + 1 + ⌊(4z + 2H − 2)/(β − 2)⌋  Z z  , 0 ≤ z < b, ds 2 ϕ(z) = Φ(z) = . 4M + 1  ϕ(s) 0  , z ≥ b, 2 The function ϕ is nondecreasing and ϕ(z) ≥ M + 1/2. The preceding bounds on δi give zi+2 − zi ≤ 2ϕ(zi ). Therefore zi+2 − zi Φ(zi+2 ) − Φ(zi ) ≤ ≤ 2. ϕ(zi ) Since Φ(z0 ) = 0 and Φ(z1 ) ≤ 1, induction on the even and odd indices yields Φ(zτ +1 ) ≤ τ + 1. We now evaluate this integral. Since zτ +1 > b, substitution in its first part gives Φ(zτ +1 ) =

β−2 2

Z 2M

3H + 4M + τ − M β ds + . M + 1 + ⌊s⌋ 4M + 1 (2H−2)/(β−2)

For fixed β, this expression is increasing in H. Indeed, away from its finitely many breakpoints, its derivative is 3 1 3 1 − ≥ − > 0. 4M + 1 M + 1 + ⌊(2H − 2)/(β − 2)⌋ 4M + 1 2M + 1 Here we used H ≥ βM/2 and M ≥ 1. We may therefore lower-bound the expression by substituting H = βM/2. At this value, the lower endpoint of the integral is M + (2M − 2)/(β − 2). Also, Z 2M M

ds = M + 1 + ⌊s⌋

3M X r=2M +1

1 . r

The omitted initial interval contributes at most (2M − 2)/((β − 2)(2M + 1)). Consequently, Φ(zτ +1 ) ≥

β−2 2

3M X r=2M +1

1 M −1 βM/2 + 4M + τ − + . r 2M + 1 4M + 1

Combining this with Φ(zτ +1 ) ≤ τ + 1 and rearranging gives β ≤ cM τ + 2 +

cM (M − 1) , 4M + 2

contradicting our choice of β. It remains to bound cM . For M = 1, we have cM = 3 ≤ 8/(1 + 4 ln(3/2)) ≈ 3.05. For M ≥ 2, convexity of 1/x and the trapezoidal rule give 3M X r=2M +1

1 1 ≥ ln(3/2) − . r 12M 41

Hence 

1 4+ M

3M X



r=2M +1

ln(3/2) − 1/3 1 1 ≥ 4 ln(3/2). ≥ 4 ln(3/2) + − r M 12M 2

The last inequality uses (ln(3/2) − 13 )/M ≥ 1/(12M 2 ), which holds for M ≥ 2 and fails for M = 1. This proves the second bound.

C.2

The randomized bound

Lemma 14. The optimal value z ∗ of (4) satisfies 1 z∗ ≤ τ + . 2 Consequently, for d = d(u, v), ˆ v)] ≤ E[d(u,



   8 4 8d + 4 k+6 d≤ k + 6 d + k. 3d + 1 3 9

The expectation is over the source’s choice, with the preprocessing fixed. Proof. By the finite minimax theorem, it suffices to show that for every distribution of an integer D ∈ [M, 3M ], some available choice has expected extra cost at most   1 τ+ E[γ(D)] + 6M − 2. 2 Fix such a distribution, and put C = min {4hi (u) + 2i + 2H Pr[D ≥ δi ]} . 0≤i<τ

Since h0 (u) = 0 and δ0 = h1 (v) ≤ M , index 0 gives C ≤ 2H and represents the fallback route. Every other index with δi ≤ M has value greater than 2H, so it cannot minimize this expression. For a minimizing index i ≥ 1, the choice t = δi is available and has expected extra cost C + 2δi − 2 ≤ C + 6M − 2. Thus it remains to prove  C≤

τ+

1 2

 E[γ(D)].

Let f be the quantile function of D: f (α) = min{d ∈ supp(D) : Pr[D ≤ d] > α},

0 ≤ α < 1.

It is nondecreasing and satisfies M ≤ f ≤ 3M . Moreover, Pr[D ≥ a] ≥ 1 − α

=⇒

a ≤ f (α).

Indeed, if f (α) < a, then Pr[D ≤ f (α)] ≤ Pr[D < a] ≤ α, contrary to its definition. Let r = C/(2H) ∈ (0, 1]. As in the deterministic proof, set zi = hi (u) +

i 2

(0 ≤ i ≤ τ ),

zτ +1 = H + M +

τ +1 . 2

The height inequalities give z0 = 0,

1 z1 ≤ M + , 2

zi+2 − zi ≤ M + 1 + δi 42

(0 ≤ i < τ ).

For every i with zi < rH/2, the definition of C implies Pr[D ≥ δi ] ≥ r −

2zi . H

The quantile property therefore gives δi ≤ f Define

  2zi 1−r+ . H

 M + 1 + f (1 − r + 2z/H)   , 0 ≤ z < rH/2, 2 ϕ(z) =   4M + 1 , z ≥ rH/2, 2

Z z Φ(z) = 0

ds . ϕ(s)

The function ϕ is nondecreasing and ϕ ≥ M + 12 . The preceding inequalities, together with δi ≤ 3M , give zi+2 − zi ≤ 2ϕ(zi ). Hence Φ(zi+2 ) − Φ(zi ) ≤ 2. Since Φ(z0 ) = 0 and Φ(z1 ) ≤ 1, induction on the two parities yields Φ(zτ +1 ) ≤ τ + 1. Evaluating the integral gives Z 1 H

dα (2 − r)H + 2M + τ + 1 + ≤ τ + 1. M + 1 + f (α) 4M + 1 1−r

Equivalently, 

Z 1

dα H (4M + 1) +2−r 1−r M + 1 + f (α) Put

 ≤ 4M τ + 2M.

 Z 1 1 dα . I=E = M +1+D 0 M + 1 + f (α) 

R 1−r Since f ≥ M , the part 0 dα/(M + 1 + f (α)) of I is at most (1 − r)/(2M + 1), and I ≥ 1/(4M + 1) since f ≤ 3M . Consequently, Z 1
dα + 2 − r ≥ r 1 + (4M + 1)I . (4M + 1) M + 1 + f (α) 1−r 
 +2 Indeed, the left side minus the right side is at least (1 − r) (4M + 1) I − 2M1+1 + 2 ≥ (1 − r) 2M 2M +1 ≥ 0. Using C = 2rH, we obtain 8M τ + 4M C≤ . 1 + (4M + 1)I For every d ≥ M ,   4M + 1 ≥ 8M. γ(d) 1 + M +1+d Indeed, subtracting 8M from the left-hand side gives
4(d − M ) 2d2 + (6M + 5)d + 2M + 2 ≥ 0. (3d + 1)(M + 1 + d)

43

By the Cauchy–Schwarz inequality, "s

E[γ(D)] 1 + (4M + 1)I ≥

E



4M + 1 γ(D) 1 + M +1+D

#!2

≥ 8M. Combining the last two bounds proves  C≤

1 τ+ 2

 E[γ(D)].

Minimax now gives z ∗ ≤ τ + 21 . Finally, the program’s constraints imply   1 ˆ γ(d) + 6M − 2. E[d(u, v)] ≤ d + τ + 2 Using τ ≤ k − 1, M ≤ d, and γ(d) ≥ 83 d, this is at most kγ(d) + 6d. The second bound in the statement follows from 8 4d 8 4 γ(d) = d + ≤ d+ . 3 3(3d + 1) 3 9

D

The deterministic name-independent bound

This appendix proves Lemma 18 and shows that it is tight. Fix u as in Section 6.1, with the gaps ga as there, and sσ (d) and β(σ) as in Section 6.2. We write ha = ha (u). Let ρ = 21/(k−1) and λ = 1/(ρ − 1), so ρ = 1 + 1/λ and ρk−1 = 2. P Valid sequences. For a sequence σ = (i1 < · · · < im ) of levels with i1 = 0, let St = s≤t his . We call σ valid if St ≤ λgit−1 for every 2 ≤ t ≤ m. If a valid σ ends at im = k − 1, then β(σ) ≤ 4λ. Indeed, fix d > 0 and let t = sσ (d). If t = 1, the sum in β(σ) is h0 = 0. Otherwise, git−1 ≤ 2d by the minimality of t, so d2 St ≤ d2 λgit−1 ≤ 4λ. Since 4λ = 4/(21/(k−1) − 1), it suffices to find a valid sequence that ends at k − 1. Cheapest valid sequences. A level a is reachable if a valid sequence ends at a. Its cost Ca is the smallest sum Sm of such a sequence, and its budget is Ra = λga − Ca . Level 0 is reachable with C0 = 0. Appending a level b > a to a valid sequence that ends at a keeps it valid if and only if its sum plus hb is at most λga . Hence b is reachable if and only if hb ≤ Ra for some reachable a < b. A cheapest valid sequence ending at a has the largest budget among all valid sequences ending at a, so Cb = hb + eb ,

where eb = min{Ca | a < b is reachable and Ra ≥ hb }.

Since level 0 has cost 0, eb > 0 implies hb > R0 . When the levels 0, . . . , L are reachable, let Xa = maxa′ ≤a Ra′ for a ≤ L, and for X0 < y ≤ XL , let u(y) = min{a | Xa ≥ y}. The level u(y) is a new maximum, so Ru(y) = Xu(y) ≥ y. Since λga = ha + Ra + ea , we have ha+1 = ha + ga = ρha + (Ra + ea )/λ, and hence hL+1 =

1 X L−a ρ (Ra + ea ). λ a≤L

Lemma 24. For every 0 ≤ L ≤ k − 2, the levels 0, . . . , L + 1 are reachable and hL+1 ≤ (ρL+1 − 1)XL . 44

(18)

For L = k − 2, the lemma shows that k − 1 is reachable, which proves Lemma 18. Proof. We use induction on L. For L = 0, h1 = g0 = R0 /λ = (ρ − 1)X0 ≤ X0 , so level 1 is reachable. Let L ≥ 1. By the induction hypothesis, the levels 0, . . . , L are reachable, and ha ≤ (ρa − 1)Xa−1 for 1 ≤ a ≤ L. It suffices to show hL+1 ≤ (ρL+1 − 1)XL . Then hL+1 ≤ XL since ρL+1 ≤ 2, so level L + 1 is reachable. The slack. Let na = eaP − (Xa − Ra ) be the part of the cost ea that exceeds the deficit Xa − Ra of the budget of a. By (18) and a≤L ρL−a = λ(ρL+1 − 1), X
X L−a ρ ρL−a na , λ (ρL+1 − 1)XL − hL+1 = (XL − Ra − ea ) = G − a≤L

where G=

X

ρL−a (XL − Xa ) =

a≤L

X

(19)

a≤L

λ ρL+1 − ρL+1−a (Xa − Xa−1 ) =

Z XL γ(y) dy X0

1≤a≤L

for γ(y) = λ(ρL+1 − ρL+1−u(y) ). We also set γ(y) = λ(ρL+1 − 1) for y > XL . Since u(y) is nondecreasing and at most L, γ is nondecreasing. So G grows whenever the largest budget grows, and it remains to show that G pays for the costs na . The cost of a predecessor. Let 1 ≤ a ≤ L with ea > 0, let q = u(ha ), and let ε = ρq − 1. We claim that 1 ≤ q < a and ea < εha /(1 − ε). Since ea > 0, ha > R0 = X0 , so q ≥ 1. Since a is reachable, some a′ < a has Ra′ ≥ ha , so q < a, and ε < ρk−1 − 1 = 1. Level q has Rq ≥ ha , so ea ≤ Cq = hq + eq . By the induction hypothesis and Xq−1 < ha , we have hq ≤ (ρq − 1)Xq−1 < εha . If eq > 0, the same argument for q gives a ′ level q ′ < q with eq ≤ hq′ + eq′ and hq′ < (ρq − 1)hq ≤ εhq < ε2 ha . We repeat until the cost is 0, and get 2 ea < ha (ε + ε + · · · ) = εha /(1 − ε). One level.

Let 1 ≤ a ≤ L with na > 0. Then ea ≥ na > 0, and we let q and ε be as above. We claim that ρL−a na < ga γ(ha ) = λga ρL+1−q (ρq − 1).

(20)

Let ψ = ρa+1−q (ρq − 1). Since λga = ha + Ra + ea = ha + Xa + na , the claim reads na < (ha + Xa + na )ψ. It holds if ψ ≥ 1. Otherwise, it reads na (1 − ψ) < (ha + Xa )ψ. Let x = ρa and v = ρq , so ε = v − 1 and ψ = ρx(v − 1)/v. By the induction hypothesis, ha ≤ (x − 1)Xa−1 ≤ (x − 1)Xa , so ha + Xa ≥ ha x/(x − 1). Since na ≤ ea < ha (v − 1)/(2 − v), it suffices that v−1 x ψ ≤ · . 2−v x−1 1−ψ
Multiplying out, this is (x − 1) v − ρx(v − 1) ≤ ρx2 (2 − v), that is, f (v) = ρx(x + 1) − v(ρx + x − 1) ≥ 0. k−2 Since q < a ≤ k − 2, we have v ≤ x/ρ = 2/ρ. The function f is decreasing, so it suffices that
and x ≤ ρ f (x/ρ) = xρ ρ2 + 1 − x(1 + ρ − ρ2 ) ≥ 0. This is clear if 1 + ρ − ρ2 ≤ 0. Otherwise, x ≤ 2/ρ gives

f (x/ρ) ≥

 x(ρ − 1)(ρ + 1)(ρ + 2) x 2 2 ρ + 1 − (1 + ρ − ρ2 ) = ≥ 0. ρ ρ ρ2

45

All levels. The intervals (ha , ha+1 ], for a ≤ L, are disjoint. If na > 0, then ha > X0 , and γ(y) ≥ γ(ha ) for Rh y > ha since γ is nondecreasing. Hence (20) gives ρL−a na < haa+1 γ(y) dy. Summing over these levels gives X a≤L

ρL−a na ≤

Z max{XL ,hL+1 }

γ(y) dy = G + λ(ρL+1 − 1) max{0, hL+1 − XL },

X0

with strict inequality if some na > 0. Suppose that hL+1 > XL . If no na is positive, the right side of (19) is at least G ≥ 0, so hL+1 ≤ (ρL+1 −1)XL ≤ XL , a contradiction. Otherwise, (19) and the strict inequality give (2−ρL+1 )hL+1 < 0, contradicting ρL+1 ≤ 2. Hence hL+1 ≤ XL , and (19) gives (ρL+1 −1)XL −hL+1 ≥ 0. A tight example. The bound of Lemma 18 is tight. Let ga = ρa for a < k − 1, so ha = λ(ρa − 1) and hk−1 = λ. Let σ be a sequence, and let a be its last level before k − 1. Then ha + hk−1 = λρa = λga , and every level of σ before k − 1 has gap at most ga . So for d > ga /2, we have sσ (d) = m, and 2 X 2λga his ≥ , d d s≤m

which tends to 4λ as d tends to ga /2. Hence β(σ) ≥ 4λ for every σ, and β ∗ = 4λ for these gaps.

E

Proofs of the name-independent worst-case bounds

In this section, we prove the bounds of Section 7, using its notation.

E.1

The deterministic bound

Lemma 19. The deterministic optimization satisfies ∗ βdet ≤

8(k − 1) + 8. ln 2

Consequently, the deterministic routing scheme has stretch at most 8(k − 1) + 9. ln 2 Proof. We exhibit a suitable sequence of rounded geometric guesses. For a shift x ∈ (0, 1), let tj = M 2j+x ,

Dj = ⌈tj ⌉ − 1,

j = 0, 1, . . . .

Stop at the first guess at least n − 1, replacing that guess by n − 1. Since c is nondecreasing, this replacement can only decrease the cost bound. We analyze the sequence before the replacement and then choose its shift. Fix an integer d ≥ M , and let J be the first index with DJ ≥ d. If J ≥ 1, the preceding guess failed to cover d, so d ≥ ⌈tJ−1 ⌉ = ⌈tJ /2⌉. This also holds when J = 0, since t0 /2 < M ≤ d. In particular, tJ ≤ 2d, and the radius terms satisfy 2

J X

Dj ≤ 2

j=0

J X

tj < 4tJ ≤ 8d.

j=0

We bound the height and index costs together: 4hi (u) + 2i =

X r<i

46

(4gr + 2).

For each finite gap, define

n l g mo r , ar = max M, 2 and let t∗r (x) be the first value tj > ar . A gap can contribute at guess Dj only if gr ≤ 2Dj , which, by integrality, is equivalent to tj > ⌈gr /2⌉. Thus it contributes only from t∗r (x) onward. Suppose that there are ℓ ≥ 1 guesses from t∗r (x) through tJ . The gap’s total contribution is at most ℓ(4gr + 2), and   d ≥ 2ℓ−2 t∗r (x) . We use the elementary inequality ℓ ⌈2ℓ−2 t⌉

≤

2 , ⌈t⌉

t > 1,

ℓ ≥ 1.

For ℓ = 1, it follows from ⌈t⌉ ≤ 2⌈t/2⌉. For ℓ ≥ 2, writing m = ⌈t⌉ ≥ 2 gives ⌈2ℓ−2 t⌉ ≥ 2ℓ−2 (m − 1) + 1 ≥

ℓm . 2

Consequently, the contribution of gap r is at most 8gr + 4 d. ⌈t∗r (x)⌉ Define F (x) =

k−2 X

8gr + 4 . ⌈t∗r (x)⌉ r=0

The preceding bounds hold simultaneously for every integer d ≥ M , and give J X

c(Dj ) ≤ (F (x) + 8)d.

j=0

It remains to choose a shift with F (x) ≤ 8(k − 1)/ ln 2. For this purpose only, let X be uniform on (0, 1). For each r, the ratio t∗r (X)/ar has the same distribution as 2X . Hence   Z 8gr + 4 8gr + 4 2ar dt E . = ⌈t∗r (X)⌉ ln 2 t⌈t⌉ ar For every positive integer a, Z 2a a

2a X 1 m dt = ln t⌈t⌉ m=a+1 m m − 1 2a X 1 − 1/(2m) m(m − 1) m=a+1  X  2a 1 1 ≤ 1− 4a m=a+1 m(m − 1)

≤

=

4a − 1 2 ≤ . 8a2 4a + 1

The first inequality follows by integrating the convex function 1/t over each interval [m − 1, m] and bounding its integral by the trapezoid area.

47

Since gr ≤ 2ar , we conclude that   16ar + 4 2 8 8gr + 4 ≤ · = . E ⌈t∗r (X)⌉ ln 2 4ar + 1 ln 2 Summing over the k − 1 finite gaps yields 8(k − 1) . ln 2

E[F (X)] ≤

Therefore some shift x satisfies the same bound. The source can choose such a shift deterministically, since F depends only on its own gaps. ∗ The resulting sequence has extra stretch at most 8(k − 1)/ ln 2 + 8. Hence βdet ≤ 8(k − 1)/ ln 2 + 8, and ∗ the stretch is at most 1 + βdet .

E.2

The randomized bound

Lemma 20. Using the guesses Dj =

  1 j+X 1 M+ e − , 4 4

j = 0, 1, . . . ,

where X is uniform on [0, 1), the randomized routing scheme satisfies ˆ v)] ≤ (8k + 2e − 7)d(u, v) + 2k − 2. E[d(u, The expectation is over the source’s random shift, with the preprocessing fixed. Proof. Fix d = d(u, v) ≥ M . Let j ∗ be the first index with Dj ∗ ≥ d. The visit at this index succeeds, so 1 j+X ˆ v) ≤ d + P and averaging over the random shift d(u, Dj <e(d+1/4)−1/4 c(Dj ). Substituting t = (M + 4 )e gives Z e(d+1/4) c(t − 1/4) ˆ v)] ≤ d + E[d(u, dt. t M +1/4 We now bound the height and index costs together: 4hi (u) + 2i = 4

X r<i

1 gr + 2

 .

For every r < i(t − 1/4), the choice of the level gives gr ≤ 2(t − 1/4),

and hence

gr +

1 ≤ 2t. 2

For r = 0, the same conclusion follows from g0 ≤ 2M and t ≥ M + 1/4. Fix a finite gap gr , and write a = gr + 21 . Its contribution to the integral is zero if a ≥ 2e(d + 14 ). Otherwise, its contribution is at most 4a ln

e(d + 1/4) 2e(d + 1/4) ≤ 4a ln max{M + 1/4, a/2} a   1 ≤8 d+ . 4

The last inequality follows by maximizing a ln(2e(d + 14 )/a) over a > 0. Summing over the k − 1 finite gaps bounds the combined height and index costs by 8(k − 1)d + 2(k − 1). 48

The remaining term in c(t − 1/4) is 2t − 21 . Since M ≥ 1, Z e(d+1/4) M +1/4

2t − 1/2 dt ≤ 2 (e(d + 1/4) − (M + 1/4)) t ≤ 2ed.

Adding the shortest-path distance and the two integral bounds yields
ˆ v)] ≤ 8(k − 1) + 2e + 1 d + 2(k − 1), E[d(u, as claimed.

F

Weighted graphs

Our average-storage schemes work in positively weighted graphs with the same stretch bounds. In this section, we extend our schemes with worst-case storage to weighted graphs. For every 0 < ε < 1, our labeled schemes have stretch ≈ (1 + ε)3.42k + O(1) and expected stretch ≈ (1 + ε)3.07k + O(1) (Theorems 9 and 10), 2 2 and our name-independent schemes have stretch 128 5 (1 + ε) k + O(1) ≈ 25.6(1 + ε) k and expected stretch √ 4e+20 e 2 2 e −1 n1/k log ∆) local (1 + ε) k + O(1) ≈ 14.62(1 + ε) k (Theorems 11 and 12). All of them use O(ε 3 storage at every vertex, where ∆ is the aspect ratio of the graph. For small enough ε, the labeled schemes improve the (4 − α)k − β of Chechik [Che13a], for small constants α, β > 0. The name-independent schemes improve the 96k of Abraham, Gavoille, and Malkhi [AGM04].

F.1

Labeled routing

The additional traversals made by the distributed tree search may be expensive in a weighted graph. To control their weight, we preprocess graphs obtained by deleting heavy edges. The source uses the destination label to select one of these graphs, and performs both the visit and the fallback route in the selected graph. Preprocessing. define

Normalize the minimum edge weight to 1, and write ∆ = diam(G). Fix 0 < ε < 1, and Wj = (1 + ε)j ,

Gj = (V, {e ∈ E : ℓ(e) ≤ Wj }),

for   0 ≤ j ≤ J = log1+ε (2∆) . We call each Gj a layer. Its edges retain their original weights and ports. Perform the preprocessing of the preceding sections separately in every connected component of every e layer. Use the global parameter S = ⌈n1/k ⌉. As in Section 5.2, every vertex belongs to O(S) cluster trees in j j i+1 each layer, and every level-i cluster has at most 4S vertices. Write pi (x), hi (x), and Bj (x) for the pivots, heights, and bunches in Gj . For each cluster tree, construct the prefix search structures of Section 5.2. A prefix contains the first min{2ℓ , |Cj (w)|} vertices in nondecreasing weighted distance from the root w. Since edge weights are positive, each prefix contains the ancestors of its vertices and forms a subtree. The records store names and routing labels in the full cluster tree. Each vertex stores the information of Section 5.2 for every layer. In addition, for every root in its bunch, it stores its exact distance to that root. The explicit level-0 dictionaries also store exact root distances. These distances allow the source to bound the fallback route before sending the message. The label of v contains its component identifier and its pivot and tree-label information for every layer. Thus the source can identify layers in which u and v are connected and compute the usual routing quantities within each such layer.

49

Weighted tree searches. Use the branching parameter 8S in the distributed indices. The same counting argument as in Lemma 12 bounds the number of additional two-edge traversals in a level-i search by i. Indeed, each additional index step reduces the number of possible record holders by a factor of at least 8S. One further traversal may be needed to read the root table stored off the initial root path, which gives i + 1 in total. If the host tree has radius at most R and lies in Gj , a lookup therefore costs at most R + 2(i + 1)Wj . An unsuccessful lookup followed by a return to the root costs at most 2R + 2(i + 1)Wj . After a successful lookup, the retrieved full-tree label allows delivery from the record holder to v at additional cost at most R + dGj (w, v). For a requested radius R, the root selects the smallest prefix containing all cluster vertices at distance at most R. The preceding prefix, which hosts the search structure, has radius at most R. Thus the prefix construction supports every requested radius, without rounding R. There are O(log n) prefixes per cluster. Choose their preorder blocks independently and fix a placement e satisfying the simultaneous storage bound, as in Section 5.2. The resulting tables use O((J +1)n1/k ) words at e every vertex. The labels use O(k(J +1)) words. The message carries the same routing state as in Section 5.3, together with the selected layer and search-structure identifiers. Choosing a layer. Fix a parameter 1 < c ≤ 2, to be specified separately for the deterministic and randomized choices. The source skips layers in which its component identifier differs from the destination’s. Consider a remaining layer Gj . If its bunch or explicit level-0 dictionary supplies a shortest route to v, set Mj = dGj (u, v), using the stored distance. Otherwise, let τj be the fallback level in this layer and define 
Mj = max hj1 (v), max hji+1 (u) − hji (v) , max |hji (u) − hji (v)|, 1≤i≤τj 0≤i<τj  dGj (u, pjτj (v)) − hjτj (v) . The first three terms are the lower bounds used in Section 4.3. The last term is also a lower bound, by the reverse triangle inequality. Hence Mj ≤ dGj (u, v). Every term is available at the source, including the distance to the fallback pivot, which belongs to its bunch. Select the first connected layer satisfying Mj ≤ Wj /c. For the rest of the section, write W = Wj ,

M = Mj ,

µ = W/c,

and suppress the layer superscripts on pivots and heights. Let d = dG (u, v). The selected layer satisfies M ≤ d,

µ ≤ (1 + ε)d. 50

(21)

For the first inequality, if d ≤ W , the layer retains a shortest path and M ≤ dGj (u, v) = d. If d > W , the selection condition gives M ≤ W/c < d. For the second inequality, every layer with Wj ≥ cd retains a shortest path and satisfies Mj ≤ d ≤ Wj /c. The weight of the selected layer is therefore at most c(1 + ε)d. Such a layer exists because c ≤ 2 and the preprocessing reaches 2∆. If the selected layer supplies a direct route, its length is M ≤ W/c < W . Any path using a deleted edge has weight greater than W , so this route is globally shortest. We henceforth consider the remaining case. The fallback route.

Let τ be the fallback level in the selected layer, and write H = hτ (v).

The additional term in M gives dGj (u, pτ (v)) ≤ M + H. Consequently, the fallback route in this layer has length at most dGj (u, pτ (v)) + H ≤ M + 2H ≤ d + 2H. This bound holds even when the selected layer does not preserve dG (u, v). The definition of M , together with M ≤ µ, also gives h1 (u), h1 (v) ≤ µ, hi+1 (u) ≤ hi (v) + µ

(0 ≤ i < τ ),

|hi (u) − hi (v)| ≤ µ

(1 ≤ i ≤ τ ).

In particular, H ≤ (2τ − 1)µ, The cost of a visit. Then

hi+1 (v) − hi (u) ≤ 3µ

(0 ≤ i < τ ).

Call a level 1 ≤ i < τ considered if hi+1 (v) − hi (u) > µ. Let i be a considered level. hi+1 (u) ≥ hi+1 (v) − M > hi (u).

Thus pi (u) is a level-i center and u ∈ Cj (pi (u)). The message routes to pi (u) and searches with radius R = hi+1 (v). If the search succeeds, it uses the retrieved label to reach v. Otherwise, it returns to u and takes the fallback route in the selected layer. Failure implies d ≥ min{W, hi+1 (v) − hi (u)}. Indeed, below this threshold the layer preserves the original distance, and dGj (pi (u), v) ≤ hi (u) + d < hi+1 (v) = R. The destination then belongs to the pivot’s cluster and lies within the searched radius. The complete route satisfies ˆ v) ≤ d + 2hi (u) + 2hi+1 (v) + 2(i + 1)W d(u, + 2H 1[d ≥ min{W, hi+1 (v) − hi (u)}].

(22)

On failure, this follows from the return cost and the fallback bound. On success with d < W , the layer preserves the distance, so delivery from the record holder gives the same bound without the indicator term. On success with d ≥ W , cluster membership gives dGj (pi (u), v) < hi+1 (v) = R. The successful route therefore costs at most hi (u) + 3R + 2(i + 1)W . Since R ≤ H, this is bounded by (22), whose indicator is then 1. 51

The quantities used in the optimization.

For each considered level, define

ai = 4hi (u) + 2iW,

ti = min{W, hi+1 (v) − hi (u)}.

Here ai is the part of the visit cost retained in the optimization, and ti is its failure threshold. The remaining cost satisfies
2hi (u) + 2hi+1 (v) + 2(i + 1)W − ai = 2 hi+1 (v) − hi (u) + 2W ≤ (6 + 2c)µ. Thus ˆ v) ≤ d + ai + 2H 1[d ≥ ti ] + (6 + 2c)µ. d(u,

(23)

We optimize over s ≥ µ, where s stands for max{d, µ}. Every considered threshold satisfies µ < ti ≤ W = cµ. A level with hi+1 (v) − hi (u) ≤ µ would have its indicator equal to 1 throughout this range, and would therefore be dominated by the fallback route. Although the actual distance may be smaller than µ, (21) gives max{d, µ} ≤ (1 + ε)d. Replacing d by max{d, µ} in the indicator can only increase the bound. We can therefore use an optimization over s ≥ µ and account for this replacement by a factor of 1 + ε. Deterministic routing. to s ≥ µ is

Take c = 2. For a considered level i, the largest ratio of the retained extra cost  max

ai ai + 2H , µ ti

 .

The first term is attained at the beginning of the range. The second is attained at the failure threshold. Between these points and beyond the threshold, the ratio is nonincreasing. The source compares these values with the fallback bound and computes    ai ai + 2H 2H βdet = min , min max , . i µ µ ti It then follows a minimizing route. By (23), ˆ v) ≤ d + βdet max{d, µ} + (6 + 2c)µ d(u, 
 ≤ 1 + (1 + ε) βdet + 6 + 2c d. It remains to bound βdet using the height inequalities above. Lemma 25. Let W = 2µ and  βdet = min

2H , min max i µ



ai ai + 2H , µ ti



over the considered levels i, where ai = 4hi (u)+2iW and ti = min{W, hi+1 (v)−hi (u)}. Assume h1 (u), h1 (v) ≤ µ, hi+1 (u) ≤ hi (v) + µ for 0 ≤ i < τ , and |hi (u) − hi (v)| ≤ µ for 1 ≤ i ≤ τ , and let H = hτ (v). Then βdet ≤

8τ + 4 . 1 + 6 ln(5/4)

52

Proof. Write T = βdet . The fallback option gives T ≤ 2H/µ. If T ≤ H/µ, the claim follows from H/µ ≤ 2τ − 1. We may therefore assume H 2H <T ≤ . µ µ Set q=

2H ∈ [1, 2), µT

zi =

hi (u) +i µ

(0 ≤ i ≤ τ ),

b=

T (2 − q) . 4

Since W = 2µ, we have ai /µ = 4zi . We first show that, whenever zi < b, 4zi hi+1 (v) − hi (u) ≤q+ . µ T For a level that is not considered, and also for i = 0, the left-hand side is at most 1, whereas the right-hand side is at least q ≥ 1. For a considered level, zi < b gives 4zi < T,

q+

4zi < 2. T

Since max{ai /µ, (ai + 2H)/ti } ≥ T and ai /µ = 4zi < T , we get (ai + 2H)/ti ≥ T , i.e. ti /µ ≤ q + 4zi /T , and ti /µ = min{2, (hi+1 (v) − hi (u))/µ}. Hence   hi+1 (v) − hi (u) 4zi min 2, ≤q+ < 2. µ T This proves the claim. The height inequalities give, for 0 ≤ i ≤ τ − 2, zi+2 − zi ≤ 3 +

hi+1 (v) − hi (u) . µ

Combining this with the preceding claim and the bound hi+1 (v) − hi (u) ≤ 3µ, we obtain ( 3 + q + 4zi /T, zi < b, zi+2 − zi ≤ 6, zi ≥ b. To sum these bounds, define Z min{z,b} Ψ(z) = 0

2 ds max{z − b, 0} + , 3 + q + 4s/T 3

z ≥ 0.

This function is increasing and concave: its slope decreases to 2/5 below b, then drops to 1/3. Consequently, the bound on zi+2 − zi gives Ψ(zi+2 ) − Ψ(zi ) ≤ 2. Moreover, z0 = 0, z1 ≤ 2, and the slope of Ψ is at most 2/(3 + q) ≤ 1/2. Thus Ψ(z0 ) = 0 and Ψ(z1 ) ≤ 1. Induction on the even and odd indices now gives Ψ(zτ ) ≤ τ. Since H = hτ (v) and |hτ (u) − hτ (v)| ≤ µ, H + τ ≤ zτ + 1. µ

53

Also, b=

T − H/µ H 1 ≤ ≤τ− , 2 2µ 2

so both zτ and H/µ + τ exceed b. On this interval, Ψ has slope 1/3. Hence   H 1 Ψ +τ ≤τ + . µ 3 Evaluating the integral gives  Ψ

H +τ µ

 =

T 5 3H/µ + 2τ − T ln + . 2 3+q 6

Substituting H/µ = qT /2 and rearranging, we obtain  8τ + 4 ≥ T 3q − 2 + 6 ln

5 3+q

 .

The expression in parentheses is increasing for q ≥ 1, since its derivative is 3 − 6/(3 + q) > 0. Its value at q = 1 is 1 + 6 ln(5/4). Therefore 8τ + 4 T ≤ , 1 + 6 ln(5/4) as required. Combining Lemma 25 with (23) and c = 2, we obtain    8τ + 4 ˆ d(u, v) ≤ 1 + (1 + ε) + 10 d(u, v). 1 + 6 ln(5/4) Since τ ≤ k − 1, the stretch is at most  1 + (1 + ε)

 8k − 4 + 10 . 1 + 6 ln(5/4)

Theorem 9. For every integer k ≥ 2 and every 0 < ε < 1, there is a 1 + (1 + ε)( 1+68k−4 ln(5/4) + 10) ≈
(1 + ε)3.42k + O(1) -stretch labeled compact routing scheme for weighted graphs that uses worst-case local e −1 n1/k log ∆) words, labels of O(ε e −1 k log ∆) words, and headers of O(1) e storage of O(ε words, where ∆ is the aspect ratio of the graph. e e Proof. The tables use O((J + 1)n1/k ) words at every vertex and the labels use O(k(J + 1)) words, where −1 J + 1 = O(ε log ∆). The header carries the routing state of Section 5.3 and the identifiers of the selected e layer and search structure, that is, O(1) words. The stretch bound is the bound above, by Lemma 25. Randomized routing. Keep 1 < c ≤ 2 as a parameter. Let π0 denote the probability of taking the fallback route directly, and let πi denote the probability of visiting a considered level i. The source solves minimize

z

subject to

2Hπ0 +

X

πi ai + 2H 1[s ≥ ti ] ≤ zs

i

π0 +

X

πi = 1,

i

π0 , πi ≥ 0. 54

for every s ∈ {µ, W } ∪ {ti },

The sums range over the considered levels. The program has O(k) variables and constraints, and every coefficient is known to the source. Between consecutive thresholds, the left-hand side is constant and nonnegative. The constraints therefore hold for every s ≥ µ. The source samples a route from an optimal solution. Using (23) and (21), we obtain ˆ v)] ≤ [1 + (1 + ε)(z ∗ + 6 + 2c)] dG (u, v). E[d(u, The expectation is over the source’s choice, with the preprocessing fixed. The remaining optimization analysis bounds z ∗ as a function of c and then chooses c. Lemma 26. For every 1 < c ≤ 2, let W = cµ and let z ∗ be the value of the linear program above, over the considered levels i with ai = 4hi (u) + 2iW and ti = min{W, hi+1 (v) − hi (u)}. Assume h1 (u), h1 (v) ≤ µ, hi+1 (u) ≤ hi (v) + µ for 0 ≤ i < τ , and |hi (u) − hi (v)| ≤ µ for 1 ≤ i ≤ τ , and let H = hτ (v). Then     4(c + 2) 4 1 , ρ(c) = max , . z ∗ ≤ ρ(c) τ + 2 c+3 c The minimum of ρ(c) is attained at √ c∗ =

13 − 1 , 2

ρ(c∗ ) =

√ 2(1 + 13) . 3

Proof. of the dual linear program. Let ys ≥ 0 be a dual solution, normalized P We bound every feasible solutionP by s ys s = 1, so its value is minchoice s ys · costs . Let θ = s/µ for s drawn with probability proportional to ys , and write m = E[θ]. Thus 1 ≤ θ ≤ c, and the dual value equals C/m, where     ai 2H ti 2H , min + Pr θ ≥ C = min . i µ µ µ µ The inner minimum is over the considered levels. It therefore suffices to prove   C 1 ≤ ρ(c) τ + . m 2 Set r=

Cµ ∈ (0, 1], 2H

zi =

hi (u) ci + µ 2

(0 ≤ i ≤ τ ).

Then ai /µ = 4zi . For 0 ≤ α < 1, let f (α) be the smallest value in the support of θ such that Pr[θ ≤ f (α)] > α. Define ( f (α), f (α) < c, fb(α) = 3, f (α) = c. The replacement of c by 3 accounts for the clipping in ti : a threshold equal to cµ only tells us that hi+1 (v) − hi (u) ≤ 3µ. We claim that, whenever zi < C/4,   hi+1 (v) − hi (u) 2µzi b ≤f 1−r+ . µ H For a considered level, the definition of C gives   ti 2µzi Pr θ ≥ ≥r− > 0. µ H 55

By the definition of f , this implies ti ≤f µ

  2µzi 1−r+ . H

If the right-hand side is below c, clipping has no effect, and the claim follows. Otherwise, use hi+1 (v)−hi (u) ≤ 3µ. For a level that is not considered, and for i = 0, the claim follows because its left-hand side is at most 1, whereas fb ≥ 1. As in the deterministic proof, we now bound the progress over two consecutive levels. Define Z min{z,C/4} Ψ(z) = 0

2 max{z − C/4, 0} 2 dw + . b c+4 1 + c + f (1 − r + 2µw/H)

This function is increasing and concave, since fb is nondecreasing and at most 3. The height inequalities give zi+2 − zi ≤ 1 + c +

hi+1 (v) − hi (u) . µ

Below C/4, apply the preceding claim. Above C/4, use hi+1 (v) − hi (u) ≤ 3µ. Concavity then gives Ψ(zi+2 ) − Ψ(zi ) ≤ 2. Also, z0 = 0, z1 ≤ (c + 2)/2, and the slope of Ψ is at most 2/(c + 2). Induction on the even and odd indices therefore yields Ψ(zτ ) ≤ τ. The endpoint satisfies 

 H cτ H C zτ ≥ max 0, −1 + > ≥ , µ 2 2µ 4 where the strict inequality uses c > 1 and τ ≥ 1. Moreover, cτ H + ≤ zτ + 1. µ 2 Since Ψ has slope 2/(c + 4) above C/4,  Ψ

H cτ + µ 2

 ≤τ+

2 . c+4

Writing Z 1 I=

dα

1−r 1 + c + fb(α)

and evaluating the two parts of Ψ, we obtain
H (c + 4)I + 2 − r ≤ 4τ + 2. µ It remains to bound I using m. For 1 ≤ t ≤ c, replacing t = c by 3 in the denominator gives the pointwise bound  1   , t < c, 1 2(t − 1) 1+c+t ≥ − . 1  c + 2 (c − 1)(c + 2)(c + 4)  , t=c c+4 At t = c, equality holds. For t < c, this follows from the tangent lower bound for 1/(1 + c + t) at t = 1, together with 2(c + 2) ≥ (c − 1)(c + 4), which holds as c ≤ 2. 56

Set p = (m − 1)/(c − 1) ∈ [0, 1]. Since f is the quantile function of θ, Z 1

Z 1 (f (α) − 1) dα ≤

1−r

(f (α) − 1) dα = m − 1. 0

Integrating the pointwise bound, and also using fb ≤ 3, gives I≥

r 2p − , c + 2 (c + 2)(c + 4)

I≥

r . c+4

If p ≥ r, the second bound yields C 4r ≤ m 1 + (c − 1)p

    1 4 1 τ+ ≤ τ+ . 2 c 2

If p ≤ r, the first bound yields C 4r ≤ m (1 + (c − 1)p)(1 + (r − p)/(c + 2))



1 τ+ 2

 .

For fixed p, the coefficient increases with r, so it is maximized at r = 1. Its denominator then becomes (1 + (c − 1)p)(c + 3 − p) . c+2 This is a concave quadratic in p, so its minimum on [0, 1] occurs at an endpoint. The two endpoints give respectively 4(c + 2)/(c + 3) and 4/c. Thus every dual solution has value at most ρ(c)(τ + 1/2), proving the bound on z ∗ . Finally, 4(c + 2)/(c + 3) is increasing in c, whereas 4/c is decreasing. They coincide when c2 + c − 3 = 0, giving the stated choice of c∗ . Taking c = c∗ , combining Lemma 26 with (23), and using τ ≤ k − 1, we obtain !# " √   √ 1 2(1 + 13) ˆ v)] ≤ 1 + (1 + ε) k− + 5 + 13 d(u, v). E[d(u, 3 2 √ √ Theorem 10. For
every integer k ≥ 2 and every 0 < ε < 1, there is a 1+(1+ε)( 2(1+3 13) (k− 12 )+5+ 13) ≈ (1 + ε)3.07k + O(1) -expected stretch labeled compact routing scheme for weighted graphs that uses worst-case e −1 n1/k log ∆) words, labels of O(ε e −1 k log ∆) words, and headers of O(1) e local storage of O(ε words, where ∆ is the aspect ratio of the graph.

e +1)n1/k ) words at every vertex and the labels use O(k(J e Proof. The tables use O((J +1)) words, where J +1 = −1 O(ε log ∆). The header carries the routing state of Section 5.3 and the identifiers of the selected layer and e search structure, that is, O(1) words. The expected stretch bound is the bound above, by Lemma 26.

F.2

Name-independent routing

We now consider name-independent routing with worst-case storage in weighted graphs. The source knows only the destination’s name, so it cannot use the destination’s pivot heights to select a layer or a search radius. Instead, it makes increasing guesses for d(u, v). Each guess determines a layer, a pivot to visit, and a radius to search. After an unsuccessful visit, the message returns to the source and proceeds to the next guess.

57

Preprocessing. Use the same layers Gj and cluster structures as in the labeled scheme. Within each connected component of every layer, store the source-pivot information, the explicit level-0 dictionaries, and the distributed search structures for the cluster trees. Each record contains the vertex’s name, its routing label in the full cluster tree, and its distance from the root. As before, the prefix structures support a search at any requested radius R, with all record holders at distance at most R from the root. We also keep the source-pivot information and explicit level-0 dictionaries for the original graph G. The e storage bound remains O((J + 1)n1/k ) words per vertex. The destination supplies no routing label: the required tree label is retrieved during the search. The initial lower bound. Fix a source u and a destination v ̸= u. If v ∈ C0 (u) in the original graph, route to v along a shortest path using its stored record. Otherwise, set   h1 (u) . M = max 1, 2 Then M ≤ d(u, v). Indeed, edge weights are at least 1, and d(u, v) < h1 (u)/2 would imply h1 (v) ≥ h1 (u) − d(u, v) > d(u, v), placing v in C0 (u). A visit with guess D. For a guess D ≥ M , consider every layer with Wj ≥ D. The source selects the layer minimizing the visit-cost bound defined below. For now, fix one such layer. All pivot heights and clusters refer to this layer, and we suppress the superscript j. Set h0 (u) = 0 and hk (u) = ∞, and choose i = i(D) = min {0 ≤ r < k : hr+1 (u) − hr (u) > 2D} . If i = 0, inspect the explicit dictionary of C0 (u) locally. If it contains v at distance at most D, route to v. Otherwise, this guess fails without sending the message. If i ≥ 1, route to pi (u) and search its cluster with radius R = hi (u) + D. The positive gap at level i ensures that pi (u) ∈ Ai \ Ai+1 and u ∈ C(pi (u)), so the level-i search bound applies. A search succeeds only if it finds the destination’s record and the stored root distance is at most R. This distance test is necessary because the selected prefix may also contain records of vertices beyond R. On success, use the retrieved label to reach v. On failure, return to the pivot and then to u. The guarantee of a visit. Every guess D ≥ d(u, v) succeeds. To see this, write d = d(u, v). Since Wj ≥ D ≥ d, a shortest u-to-v path is retained in Gj , and hence dGj (u, v) = d. The choice of i gives hi+1 (v) ≥ hi+1 (u) − d > hi (u) + 2D − d ≥ hi (u) + D ≥ dGj (pi (u), v). Thus v ∈ C(pi (u)), and its distance from the pivot is at most the requested radius. For i = 0, this is precisely the local dictionary test. Consequently, every failed guess certifies d(u, v) > D.

58

The cost of a visit.

For each guess, compute the following bound in every layer with Wj ≥ D: ( 0, i(D) = 0, costj (D) = 4hi (u) + 2D + 2(i + 1)Wj , i = i(D) ≥ 1.

Here i(D) and hi (u) are computed in Gj . The source chooses a layer attaining cost(D) =

min costj (D).

j: Wj ≥D

In the following bounds, j is the selected layer. A failed visit costs at most cost(D). For i ≥ 1, reaching the pivot and returning to u costs 2hi (u), while the failed search and return to the pivot cost at most 2R + 2(i + 1)Wj . Their sum is 2hi (u) + 2R + 2(i + 1)Wj = cost(D). A successful visit costs at most d(u, v) + cost(D). For i ≥ 1, the search costs at most R + 2(i + 1)Wj . Both the record holder and the destination are within distance R of the pivot, so delivery from the holder costs at most 2R. Including the initial route to the pivot, the total is at most hi (u) + 3R + 2(i + 1)Wj = cost(D) + D. If D < d(u, v), this proves the claimed bound. If D ≥ d(u, v), shortest paths are preserved in the selected layer, and the sharper delivery bound R + dGj (pi (u), v) ≤ R + hi (u) + d(u, v) gives the same conclusion. For i = 0, a successful dictionary test finds a path of length at most D ≤ Wj . This path is globally shortest, since every deleted edge has weight greater than Wj . Thus the successful route has length d(u, v), consistent with cost(D) = 0. The available guesses.

Use the finite set D = {D0 , . . . , DL },

Dℓ = min{(1 + ε)ℓ M, ∆},

where L is the first index for which DL = ∆. A schedule is an increasing sequence of guesses from D ending at ∆. The message follows this sequence until a search succeeds. Deterministic routing. Consider a schedule σ = (t0 , . . . , tq ), where tq = ∆. For a distance d ≥ M , let r be the first index with tr ≥ d. The search succeeds no later than this guess, so ˆ v) ≤ d + d(u,

r X

cost(ta ).

a=0

For M ≤ d ≤ t0 , the ratio of this extra-cost bound to d is largest at M . For tr−1 < d ≤ tr , its supremum is attained as d approaches tr−1 from above. Thus define Pr   cost(t0 ) a=0 cost(ta ) β(σ) = max , max . 1≤r≤q M tr−1 The source chooses a schedule minimizing this expression: ∗ βdet = min β(σ). σ

The resulting route satisfies ˆ v) ≤ (1 + β ∗ )d(u, v). d(u, det Unlike in the unweighted analysis, distances need not be integral. The denominators are therefore the preceding guesses themselves, with no additive 1. 59

Lemma 27. The deterministic optimization satisfies 128 (1 + ε)2 k. 5 Consequently, the deterministic routing scheme has stretch at most ∗ βdet ≤

1+

128 (1 + ε)2 k. 5

Proof. It suffices to exhibit a schedule with the claimed bound. For each r ≥ 0, round min{2r M, ∆} up to the next available guess: tr = min{t ∈ D : t ≥ min{2r M, ∆}}. Delete repetitions and stop at the first occurrence of ∆. Since consecutive available guesses differ by a factor of at most 1 + ε, we have tr ≤ (1 + ε)2r M . We first bound the sum of cost(tr ) over at most four consecutive indices r. Let t be the largest unrounded guess in this block, so its unrounded guesses belong to {t, t/2, t/4, t/8}. Choose the smallest j for which Wj is at least the largest rounded guess in this block. Then Wj ≤ (1 + ε)2 t. This layer is eligible for every guess in the block. Since cost minimizes over eligible layers, we may bound all these visits using this one layer. All heights and levels below refer to this layer. Visits with i = 0 have zero cost. For i ≥ 1, write costj (D) = 2D + 2Wj +

i−1 X

4(ha+1 (u) − ha (u)) + 2Wj .

a=0

Fix a gap g = ha+1 (u) − ha (u) that contributes to ℓ visits in the block. The selected level in this fixed layer is nondecreasing with the guess, so these visits correspond to the ℓ largest unrounded guesses, where 1 ≤ ℓ ≤ 4. At the smallest of them, the minimality of the selected level and the rounding bound give t g ≤ 2(1 + ε) ℓ−1 . 2 Thus this gap contributes at most 2



ℓ(4g + 2Wj ) ≤ (1 + ε) t ℓ

8 2ℓ−1

 +2

≤ 12(1 + ε)2 t.

The last coefficient is 10, 12, 12, 12 for ℓ = 1, 2, 3, 4, respectively. There are at most k − 1 such gaps. The remaining terms 2D + 2Wj contribute at most     1 1 1 47 2 (1 + ε)2 t ≤ 12(1 + ε)2 t. (1 + ε) t 2 1 + + + +8 = 2 4 8 4 The total cost of the block is therefore at most 12k(1 + ε)2 t. Now fix d ∈ [M, ∆], and let m be the first index with 2m M ≥ d. Then tm ≥ d and 2m M ≤ 2d. Partition the guesses indexed by 0, . . . , m into blocks of four, starting from index m and working backwards. The first block in the schedule may be shorter. Their largest unrounded guesses are 2m M, 2m−4 M, 2m−8 M, . . .. Hence m X X cost(tr ) ≤ 12k(1 + ε)2 2m M 2−4b r=0

b≥0

128 ≤ (1 + ε)2 k d. 5 The search succeeds no later than tm . Deleting repetitions or stopping earlier only decreases the accumulated cost. Thus the exhibited schedule has β(σ) at most the claimed bound, and so does the minimizing schedule. Adding d(u, v) gives the stretch bound. 60

Theorem 11. For every integer k ≥ 2 and every 0 < ε < 1, there is a (1 + 25.6(1 + ε)2 k)-stretch namee −1 n1/k log ∆) independent compact routing scheme for weighted graphs that uses worst-case local storage of O(ε e words and headers of O(1) words, where ∆ is the aspect ratio of the graph. e Proof. The tables use O((J + 1)n1/k ) words at every vertex, where J + 1 = O(ε−1 log ∆). The header carries the current guess, the selected layer, level, and search structure, and the current tree identifier, target label, e and return label, that is, O(1) words. The stretch bound is Lemma 27. Randomized routing. The source now chooses a distribution over schedules. We express this optimization using transitions between guesses, avoiding a separate variable for every schedule. Introduce a start index −1. For each −1 ≤ a < b ≤ L, let pa,b be the probability that the sampled schedule moves directly from index a to index b. An edge from −1 selects the first guess. These probabilities satisfy L X p−1,b = 1, b=0 r−1 X

pa,r =

a=−1

L X

pr,b

(0 ≤ r < L),

b=r+1

pa,b ≥ 0

(−1 ≤ a < b ≤ L).

These are the constraints for one unit of flow from the start index to L. Every such flow defines a distribution over increasing schedules ending at ∆. Fix 0 ≤ r < L and a distance d ∈ (Dr , Dr+1 ]. A transition contributes to the cost bound precisely when it selects the first guess or its preceding guess is at most Dr . The expected extra-cost bound is therefore L X

p−1,b cost(Db ) +

L r X X

pa,b cost(Db ).

a=0 b=a+1

b=0

This expression is constant throughout the interval, so its ratio to d is largest as d approaches Dr from above. The source minimizes z, subject to the flow constraints and L X

p−1,b cost(Db ) ≤ zM,

b=0 L X b=0

p−1,b cost(Db ) +

L r X X

pa,b cost(Db ) ≤ zDr

(0 ≤ r < L).

a=0 b=a+1

The first constraint bounds the cost at d = M . The program has O((L + 1)2 ) variables and O(L + 1) constraints. Given an optimal flow, the source samples the next index according to the outgoing flow at its current index. It performs the corresponding visit and, on failure, returns to u and samples the next index. Every sampled schedule ends at ∆, where success is guaranteed. If z ∗ is the optimum, then ˆ v)] ≤ (1 + z ∗ )d(u, v). E[d(u, The expectation is over the source’s choices, with the preprocessing fixed. Lemma 28. The randomized optimization satisfies   √ ln 5 4e + 20 e 2 ∗ (1 + ε) k + ≈ (1 + ε)2 (14.62k + 5.88). z ≤ 3 4 61

Consequently, the randomized routing scheme has expected Avi: I guess sleeping is overrated. stretch at most   √ 4e + 20 e ln 5 2 1+ (1 + ε) k + . 3 4 Proof. It suffices to exhibit a distribution over schedules. Choose U uniformly from [0, 1) and use the guesses M er+U , for r = 0, 1, . . ., rounding each up to the next member of D and capping it at ∆. Delete repetitions and stop at ∆. For t ≥ M , let f (t) be the cost of the rounded and capped guess, and set f (t) = 0 for 0 < t < M . The function f is nonnegative and nondecreasing: within each layer, the selected level and its cost are nondecreasing, while the set of eligible layers only shrinks. Fix d ∈ [M, ∆]. The schedule succeeds by the first unrounded guess at least d. A guess after the first contributes to the resulting cost bound exactly when its predecessor is less than d. Averaging over U therefore gives Z ed f (t) dt. (24) E[extra-cost bound at distance d] ≤ t M Indeed, the first guess accounts for t ∈ [M, eM ), and the subsequent guesses account for t ∈ [eM, ed). Deleting repeated guesses or stopping earlier only decreases the cost. We first bound a weighted average of f . For every W > 0, define f (W ) F (W ) = + 10W We claim that

Z W 0

2f (t) dt. (4t + W )2

  ln 5 . F (W ) ≤ (1 + ε)2 k + 4

(25)

For W < M , this is immediate. Otherwise, choose the smallest layer covering the rounded and capped guess corresponding to W . This layer is eligible for all smaller guesses and satisfies Wj ≤ (1 + ε)2 W . We upper-bound f using the costs in this one layer. As in the deterministic proof, a nonzero visit cost is the sum of 2D + 2Wj and one term 4g + 2Wj for each gap g below the selected level. Fix such a gap, and let a be the infimum of the unrounded guesses in [M, W ] for which it contributes. By the choice of the level and the rounding rule, g ≤ 2(1 + ε)a. Its total weight in F (W ) is at most Z W 1 2 1 + dt = . 2 10W (4t + W ) 8a + 2W a Since 4g + 2Wj ≤ (1 + ε)2 (8a + 2W ), each gap contributes at most (1+ε)2 . There are at most k −1 gaps. The remaining terms satisfy 2D +2Wj ≤ (1 + ε)2 (2t + 2W ), so their contribution is at most " # Z W 4(t + W ) 2 2 (1 + ε) + dt 5 (4t + W )2 0   ln 5 . = (1 + ε)2 1 + 4 This proves (25). To pass from this weighted average to the integral in (24), set 20 κ = √ − 2. e

62

We use the elementary inequality Z 1 x

1 + (κ/2)y 2 1 dy ≥ ln y + 4x x

(0 < x ≤ 1).

(26)

For completeness, let Γ(x) be the left-hand side minus the right-hand side. Integration and differentiation give √  e(1 + 4x) x 5 Γ(x) − Γ′ (x) = ln +√ − 1 ≥ 0, 2 5 e(1 + 4x) where the last step uses ln y + 1/y − 1 ≥ 0 for y > 0. Thus (Γ(x)/x2 )′ ≤ 0. Since Γ(1) = 0, we obtain Γ(x) ≥ 0, proving (26). It follows that, for every T > 0,  Z T Z T f (t) W2 dt ≤ 2 + κ 2 F (W ) dW. t T 0 0 To verify this, use that f is a nonnegative linear combination of step functions. For a single step f (t) = 1[t ≥ a], we have F (W ) = 0 for W < a and F (W ) = 1/(8a + 2W ) for W ≥ a. If a ≤ T , the desired inequality is precisely (26) with x = a/T , after substituting y = W/T . If a > T , both sides vanish. Values at the finitely many jump points do not affect these integrals. Using (25), we conclude Z T 0

   f (t) κ ln 5 2 dt ≤ 2 + (1 + ε) k + T. t 3 4

Take T = ed in this inequality and apply (24). The expected extra-cost bound is at most     √  κ ln 5 ln 5 4e + 20 e 2 2 e 2+ (1 + ε) k + (1 + ε) k + d= d. 3 4 3 4 This holds for every d ∈ [M, ∆]. The exhibited distribution therefore gives a feasible solution to the randomized optimization with the claimed value of z. The optimum is no larger, and adding d(u, v) gives the expected stretch bound. √

e Theorem 12. For every integer k ≥ 2 and every 0 < ε < 1, there is a 1 + 4e+20 (1 + ε)2 (k + ln45 ) ≈ 3
(1 + ε)2 (14.62k + 5.88) -expected stretch name-independent compact routing scheme for weighted graphs that e −1 n1/k log ∆) words and headers of O(1) e uses worst-case local storage of O(ε words, where ∆ is the aspect ratio of the graph.

e Proof. The tables use O((J + 1)n1/k ) words at every vertex, where J + 1 = O(ε−1 log ∆). The header carries the current guess, the selected layer, level, and search structure, and the current tree identifier, target label, e and return label, that is, O(1) words. The expected stretch bound is Lemma 28.

63

Related documents

• Undirected Network Coding and Faster External-Memory Integer Sorting#1355015
• A linear upper bound for Berge saturation numbers#1248689
• Experimental multiple-path routing algorithm#220755
• Emergent Sorting in Networks of Router Agents#622709
• Spatially Coupled MacKay-Neal Codes Achieve Capacity on BMS Channels at Fixed Degrees#1109524