A t-spanner of a point set X in a metric space (𝒳, δ) is a graph G with vertex set P such that, for any pair of points u,v ∈ X, the distance between u and v in G is at most t times δ(u,v). We study the problem of maintaining a spanner for a dynamic point set X - that is, when X undergoes a sequence of insertions and deletions - in a metric space of constant doubling dimension. For any constant ε > 0, we maintain a (1+ε)-spanner of P whose total weight remains within a constant factor of the weight of the minimum spanning tree of X. Each update (insertion or deletion) can be performed in poly(log Φ) time, where Φ denotes the aspect ratio of X. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space.

In this paper we consider the problem of approximating Euclidean distances by the infinite integer grid graph. Although the topology of the graph is fixed, we have control over the edge-weight assignment $w:E\to \mathbb{R}_{\ge 0}$, and hope to have grid distances be asymptotically isometric to Euclidean distances, that is, for all grid points $u,v$, $\mathrm{dist}_w(u,v) = (1\pm o(1))\|u-v\|_2$. We give three methods for solving this problem, each attractive in its own way. * Our first construction is based on an embedding of the recursive, non-periodic pinwheel tiling of Radin and Conway into the integer grid. Distances in the pinwheel graph are asymptotically isometric to Euclidean distances, but no explicit bound on the rate of convergence was known. We prove that the multiplicative distortion of the pinwheel graph is $(1+1/Θ(\log^ξ\log D))$, where $D$ is the Euclidean distance and $ξ=Θ(1)$. The pinwheel tiling approach is conceptually simple, but can be improved quantitatively. * Our second construction is based on a hierarchical arrangement of "highways." It is simple, achieving stretch $(1 + 1/Θ(D^{1/9}))$, which converges doubly exponentially faster than the pinwheel tiling approach. * The first two methods are deterministic. An even simpler approach is to sample the edge weights independently from a common distribution $\mathscr{D}$. Whether there exists a distribution $\mathscr{D}^*$ that makes grid distances Euclidean, asymptotically and in expectation, is major open problem in the theory of first passage percolation. Previous experiments show that when $\mathscr{D}$ is a Fisher distribution, grid distances are within 1\% of Euclidean. We demonstrate experimentally that this level of accuracy can be achieved by a simple 2-point distribution that assigns weights 0.41 or 4.75 with probability 44\% and 56\%, respectively.

The Capacitated Sum of Radii problem involves partitioning a set of points $P$, where each point $p\in P$ has capacity $U_p$, into $k$ clusters that minimize the sum of cluster radii, such that the number of points in the cluster centered at point $p$ is at most $U_p$. We begin by showing that the problem is APX-hard, and that under gap-ETH there is no parameterized approximation scheme (FPT-AS). We then construct a $\approx5.83$-approximation algorithm in FPT time (improving a previous $\approx7.61$ approximation in FPT time). Our results also hold when the objective is a general monotone symmetric norm of radii. We also improve the approximation factors for the uniform capacity case, and for the closely related problem of Capacitated Sum of Diameters.

Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating DAGs D_1,… ,D_g such that all distances are approximately preserved: for every pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein [STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This paper initiates the study of Steiner DAG cover, where the DAGs are allowed to contain Steiner points. We obtain Steiner DAG covers on the important classes of planar digraphs and low-treewidth digraphs. Specifically, we show that any digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover. We also demonstrate a stark difference between Steiner and non-Steiner DAG covers. As a lower bound, we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs.

Given a weighted digraph \(G = (V,E,w)\), a stochastic embedding into DAGs is a distribution \(\mathcal D\) over pairs of DAGs (\(D_1,D_2\)) such that for every \(u, v\): (1) the reachability is preserved: \(u \rightsquigarrow_{G}\ v\) (i.e., \(v\) is reachable from \(u\) in \(G\)) implies that \(u \rightsquigarrow_{D_1} v\) or \(u \rightsquigarrow_{D_2} v\) (but not both), and (2) distances are dominated: \(d_G(u, v) = \min\{d_{D_1}(u, v), d_{D_2}(u, v)\}\). The stochastic embedding \(\mathcal D\) has expected distortion \(t\) if for every \(u, v \in V\), \begin{equation} \mathbb{E}_{(D_1, D_2) \sim \mathcal{D}}\left[ d_{D_1}(u,v)\cdot \mathbb{1}[u \rightsquigarrow_{D_1} v] + d_{D_2}(u,v)\cdot \mathbb{1}[u \rightsquigarrow_{D_2} v]\right]\le t \cdot d_G(u,v)\,.\end{equation} Finally, the sparsity of \(\mathcal D\) is the maximum number of edges in any of the DAGs in its support.

Given a metric space $(X,d_X)$, a $(β,s,Δ)$-sparse cover is a collection of clusters $\mathcal{C}\subseteq P(X)$ with diameter at most $Δ$, such that for every point $x\in X$, the ball $B_X(x,\fracΔβ)$ is fully contained in some cluster $C\in \mathcal{C}$, and $x$ belongs to at most $s$ clusters in $\mathcal{C}$. Our main contribution is to show that the shortest path metric of every $K_r$-minor free graphs admits $(O(r),O(r^2),Δ)$-sparse cover, and for every $ε>0$, $(4+ε,O(\frac1ε)^r,Δ)$-sparse cover (for arbitrary $Δ>0$). We then use this sparse cover to show that every $K_r$-minor free graph embeds into $\ell_\infty^{\tilde{O}(\frac1ε)^{r+1}\cdot\log n}$ with distortion $3+ε$ (resp. into $\ell_\infty^{\tilde{O}(r^2)\cdot\log n}$ with distortion $O(r)$). Further, among other applications, this sparse cover immediately implies an algorithm for the oblivious buy-at-bulk problem in fixed minor free graphs with the tight approximation factor $O(\log n)$ (previously nothing beyond general graphs was known).

We study efficient algorithms for the Euclidean $k$-Center problem, focusing on the regime of large $k$. We take the approach of data reduction by considering $\alpha$-coreset, which is a small subset $S$ of the dataset $P$ such that any $\beta$-approximation on $S$ is an $(\alpha + \beta)$-approximation on $P$. We give efficient algorithms to construct coresets whose size is $k \cdot o(n)$, which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time $O(1)$-approximation when $k = n^c$ for any $0 < c < 1$. We validate the performance of our coresets on real-world datasets with large $k$, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to $4$ times, while still achieving similar clustering cost. Technically, one of our coreset results is based on a new efficient construction of consistent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces.

Realistic metric spaces (such as road/transportation networks) tend to be much more tractable then general metrics. In an attempt to formalize this intuition, Abraham et. al. (SODA 2010, JACM 2016) introduced the notion of highway dimension. A weighted graph G has highway dimension h if for every ball B of radius ≈ 4r there is a hitting set of size h hitting all the shortest paths of length > r in B. Unfortunately, this definition fails to incorporate some very natural metric spaces such as the grid graph, and the Euclidean plane.

It was conjectured by Gupta et al. that every planar graph can be embedded into \(\ell_{1}\) with constant distortion. However, given an \(n\) -vertex weighted planar graph, the best upper bound on the distortion is only \(O(\sqrt{\log n})\) , by Rao. In this article, we study the case where there is a set \(K\) of terminals, and the goal is to embed only the terminals into \(\ell_{1}\) with low distortion. In a seminal article, Okamura and Seymour showed that if all the terminals lie on a single face, they can be embedded isometrically into \(\ell_{1}\) . The more general case, where the set of terminals can be covered by \(\gamma\) faces, was studied by Lee and Sidiropoulos and Chekuri et al. The state of the art is an upper bound of \(O(\log\gamma)\) by Krauthgamer, Lee and Rika. Our contribution is a further improvement on the upper bound to \(O(\sqrt{\log\gamma})\) . Since every planar graph has at most \(O(n)\) faces, any further improvement on this result will be a major breakthrough, directly improving upon Rao's long standing upper bound. Moreover, it is well known that the flow-cut gap equals to the distortion of the best embedding into \(\ell_{1}\) . Therefore, our result provides a polynomial time \(O(\sqrt{\log\gamma})\) -approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by \(\gamma\) faces.

A \emph{$ν$-reliable spanner} of a metric space $(X,d)$, is a (dominating) graph $H$, such that for any possible failure set $B\subseteq X$, there is a set $B^+$ just slightly larger $|B^+|\le(1+ν)\cdot|B|$, and all distances between pairs in $X\setminus B^+$ are (approximately) preserved in $H\setminus B$. Recently, there have been several works on sparse reliable spanners in various settings, but so far, the weight of such spanners has not been analyzed at all. In this work, we initiate the study of \emph{light} reliable spanners, whose weight is proportional to that of the Minimum Spanning Tree (MST) of $X$. We first observe that unlike sparsity, the lightness of any deterministic reliable spanner is huge, even for the metric of the simple path graph. Therefore, randomness must be used: an \emph{oblivious} reliable spanner is a distribution over spanners, and the bound on $|B^+|$ holds in expectation. We devise an oblivious $ν$-reliable $(2+\frac{2}{k-1})$-spanner for any $k$-HST, whose lightness is $\approx ν^{-2}$. We demonstrate a matching $Ω(ν^{-2})$ lower bound on the lightness (for any finite stretch). We also note that any stretch below 2 must incur linear lightness. For general metrics, doubling metrics, and metrics arising from minor-free graphs, we construct {\em light} tree covers, in which every tree is a $k$-HST of low weight. Combining these covers with our results for $k$-HSTs, we obtain oblivious reliable light spanners for these metric spaces, with nearly optimal parameters. In particular, for doubling metrics we get an oblivious $ν$-reliable $(1+\varepsilon)$-spanner with lightness $\varepsilon^{-O({\rm ddim})}\cdot\tilde{O}(ν^{-2}\cdot\log n)$, which is best possible (up to lower order terms).

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an$n-\mathbf{vertex}$planar graph$G=(V, E)$undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a$(1+\epsilon)-\mathbf{approximate}$dynamic algorithm that supports edge updates and distance queries in$n^{o(1)}$time, for any$1/\mathbf{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of$\tilde{O}(\sqrt{n})$on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a$\Omega(\sqrt{n})$conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].

Low-distortional metric embeddings are a crucial component in the modern algorithmic toolkit. In an online metric embedding, points arrive sequentially and the goal is to embed them into a simple space irrevocably, while minimizing the distortion. Our first result is a deterministic online embedding of a general metric into Euclidean space with distortion if the metric has doubling dimension d), solving affirmatively a conjecture by Newman and Rabinovich (2020), and quadratically improving the dependence on the aspect ratio Φ from Indyk et al. (2010). Our second result is a stochastic embedding of a metric space into trees with expected distortion O(d·log Φ), generalizing previous results (Indyk et al. (2010), Bartal et al. (2020)).

Abstract. Given a metric space [Formula: see text], a weighted graph [Formula: see text] over [Formula: see text] is a metric [Formula: see text]-spanner of [Formula: see text] if for every [Formula: see text], [Formula: see text], where [Formula: see text] is the shortest path metric in [Formula: see text]. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points [Formula: see text], where the points are presented one at a time (i.e., after [Formula: see text] steps, we see [Formula: see text]). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a [Formula: see text]-spanner [Formula: see text] for [Formula: see text] for all [Formula: see text], while minimizing the number of edges, and their total weight. We construct online [Formula: see text]-spanners in the Euclidean [Formula: see text]-space, [Formula: see text]-spanners for general metrics, and [Formula: see text]-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a [Formula: see text]-spanner with competitive ratio [Formula: see text], bypassing the classic lower bound [Formula: see text] for lightness, which compares the weight of the spanner to that of the minimum spanning tree.

A partition \(\mathcal{P}\) of a weighted graph \(G\) is \((\sigma,\tau,\Delta)\) -sparse if every cluster has diameter at most \(\Delta\) , and every ball of radius \(\Delta/\sigma\) intersects at most \(\tau\) clusters. Similarly, \(\mathcal{P}\) is \((\sigma,\tau,\Delta)\) -scattering if instead for balls, we require that every shortest path of length at most \(\Delta/\sigma\) intersects at most \(\tau\) clusters. Given a graph \(G\) that admits a \((\sigma,\tau,\Delta)\) -sparse partition for all \(\Delta > 0\) , Jia et al. constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch \(O(\tau\sigma^{2} \log _{\tau}n)\) . Given a graph \(G\) that admits a \((\sigma,\tau,\Delta)\) -scattering partition for all \(\Delta > 0\) , we construct a solution for the Steiner Point Removal problem with stretch \(O(\tau^{3}\sigma^{3})\) . We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.

Chan, Har-Peled, and Jones [SICOMP 2020] developed locality-sensitive orderings (LSO) for Euclidean space. A $(τ,ρ)$-LSO is a collection $Σ$ of orderings such that for every $x,y\in\mathbb{R}^d$ there is an ordering $σ\inΣ$, where all the points between $x$ and $y$ w.r.t. $σ$ are in the $ρ$-neighborhood of either $x$ or $y$. In essence, LSO allow one to reduce problems to the $1$-dimensional line. Later, Filtser and Le [STOC 2022] developed LSO's for doubling metrics, general metric spaces, and minor free graphs. For Euclidean and doubling spaces, the number of orderings in the LSO is exponential in the dimension, which made them mainly useful for the low dimensional regime. In this paper, we develop new LSO's for Euclidean, $\ell_p$, and doubling spaces that allow us to trade larger stretch for a much smaller number of orderings. We then use our new LSO's (as well as the previous ones) to construct path reporting low hop spanners, fault tolerant spanners, reliable spanners, and light spanners for different metric spaces. While many nearest neighbor search (NNS) data structures were constructed for metric spaces with implicit distance representations (where the distance between two metric points can be computed using their names, e.g. Euclidean space), for other spaces almost nothing is known. In this paper we initiate the study of the labeled NNS problem, where one is allowed to artificially assign labels (short names) to metric points. We use LSO's to construct efficient labeled NNS data structures in this model.

A spanning tree T of graph G is a $\rho$-approximate universal Steiner tree (UST) for root vertex r if, for any subset of vertices S containing r, the cost of the minimal subgraph of T connecting S is within a $\rho$ factor of the minimum cost tree connecting S in G. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions.We settle these open questions by giving polynomial-time algorithms for computing both $O\left(\log ^{7} n\right)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. We reduce the existence of these objects to the previously studied cluster aggregation problem and a class of well-separated point sets which we call dangling nets. For graphs with constant doubling dimension or constant pathwidth we obtain improved bounds by deriving $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms.

In this paper we initiate the study of expander decompositions of a graph G = ( V, E) in the streaming model of computation. The goal is to find a partitioning C of vertices V such that the subgraphs of G induced by the clusters C is an element of C are good expanders, while the number of intercluster edges is small. Expander decompositions are classically constructed by a recursively applying balanced sparse cuts to the input graph. In this paper we give the first implementation of such a recursive sparsest cut process using small space in the dynamic streaming model. Our main algorithmic tool is a new type of cut sparsifier that we refer to as a power cut sparsifier - it preserves cuts in any given vertex induced subgraph (or, any cluster in a fixed partition of V) to within a (delta, epsilon)-multiplicative/additive error with high probability. The power cut sparsifier uses (O) over tilde (n/epsilon delta) space and edges, which we show is asymptotically tight up to polylogarithmic factors in n for constant delta.

Abstract. This note points out an error in the proof of Theorem 4 in the article “Metric Embedding via Shortest Path Decompositions,” SIAM J. Comput., 51 (2022), pp. 290–314, by the authors, and withdraws the associated claim of Theorem 4.

Given a curve P with points in ℝ d in a streaming fashion, and parameters ɛ > 0 and k , we construct a distance oracle that uses \(O(\frac{1}{\varepsilon })^{kd}\log \varepsilon ^{-1}\) space, and given a query curve Q with k points in ℝ d returns in \(\tilde{O}(kd)\) time a 1+ɛ approximation of the discrete Fréchet distance between Q and P . In addition, we construct simplifications in the streaming model, oracle for distance queries to a sub-curve (in the static setting), and introduce the zoom-in problem. Our algorithms work in any dimension d , and therefore we generalize some useful tools and algorithms for curves under the discrete Fréchet distance to work efficiently in high dimensions.

Cohen-Addad, Filtser, Klein and Le [FOCS’20] constructed a stochastic embedding of minor-free graphs of diameter D into graphs of treewidth $O_{\epsilon}(\log n)$ with expected additive distortion $+\epsilon D$. Cohen-Addad et al. then used the embedding to design the first quasi-polynomial time approximation scheme (QPTAS) for the capacitated vehicle routing problem. Filtser and Le [STOC’21] used the embedding (in a different way) to design a QPTAS for the metric Baker’s problems in minor-free graphs. In this work, we devise a new embedding technique to improve the treewidth bound of Cohen-Addad et al. exponentially to $O_{\epsilon}(\log \log n)^{2}$. As a corollary, we obtain the first efficient PTAS for the capacitated vehicle routing problem in minor-free graphs. We also significantly improve the running time of the QPTAS for the metric Baker’s problems in minor-free graphs from $n^{O_{\epsilon}(\log (n))}$ to $n^{O_{\epsilon}(\log \log (n))^{3}}$. Applying our embedding technique to planar graphs, we obtain a deterministic embedding of planar graphs of diameter D into graphs of treewidth $\left.O\left((\log \log n)^{2}\right) / \epsilon\right)$ and additive distortion $+\epsilon D$ that can be constructed in nearly linear time. Important corollaries of our result include a bicriteria PTAS for metric Baker’s problems and a PTAS for the vehicle routing problem with bounded capacity in planar graphs, both run in almost-linear time. The running time of our algorithms is significantly better than previous algorithms that require quadratic time. A key idea in our embedding is the construction of an (exact) emulator for tree metrics with treewidth $O(\log \log n)$ and hop-diameter $O(\log \log n)$. This result may be of independent interest.

Chan, Har-Peled, and Jones [2020] recently developed locality-sensitive ordering (LSO), a new tool that allows one to reduce problems in the Euclidean space ℝd to the 1-dimensional line. They used LSO’s to solve a host of problems. Later, Buchin, Har-Peled, and Oláh [2019,2020] used the LSO of Chan et al. to construct very sparse reliable spanners for the Euclidean space. A highly desirable feature of a reliable spanner is its ability to withstand a massive failure: the network remains functioning even if 90% of the nodes fail. In a follow-up work, Har-Peled, Mendel, and Oláh [2021] constructed reliable spanners for general and topologically structured metrics. Their construction used a different approach, and is based on sparse covers.

Spanners for low dimensional spaces (e.g. Euclidean space of constant dimension, or doubling metrics) are well understood. This lies in contrast to the situation in high dimensional spaces, where except for the work of Har–Peled, Indyk and Sidiropoulos (SODA 2013), who showed that any n-point Euclidean metric has an O(t)-spanner with $$\tilde{O}(n^{1+1/t^2})$$ edges, little is known. In this paper we study several aspects of spanners in high dimensional normed spaces. First, we build spanners for finite subsets of $$\ell _p$$ with $$1<p\le 2$$ . Second, our construction yields a spanner which is both sparse and also light, i.e., its total weight is not much larger than that of the minimum spanning tree. In particular, we show that any n-point subset of $$\ell _p$$ for $$1

We study the problem of embedding shortest-path metrics of weighted graphs into $\ell_p$ spaces. We introduce a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of shortest path decomposition (SPD) depth is inductively defined: A (weighed) path graph has SPD depth $1$. General graph has an SPD of depth $k$ if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most $k-1$. In this paper we give an $O(k^{\min\{\nicefrac{1}{p},\nicefrac{1}{2}\}})$-distortion embedding for graphs of SPD depth at most $k$. This result is asymptotically tight for any fixed $p>1$, while for $p=1$ it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth $k$ embed into $\ell_p$ with distortion $O(k^{\min\{\nicefrac{1}{p},\nicefrac{1}{2}\}})$. For $p=1$, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in $k$; moreover, for other values of $p$ it gives the first embeddings whose distortion is independent of the graph size $n$. Furthermore, we use the fact that planar graphs have SPD depth $O(\log n)$ to give a new proof that any planar graph embeds into $\ell_1$ with distortion $O(\sqrt{\log n})$. Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor.

Consider a set of voters V, represented by a multiset in a metric space (X,d). The voters have to reach a decision - a point in X. A choice p∈ X is called a β-plurality point for V, if for any other choice q∈ X it holds that |{v∈ V ∣ β⋅ d(p,v)≤ d(q,v)}| ≥|V|/2 . In other words, at least half of the voters ``prefer'' over q, when an extra factor of β is taken in favor of p. For β=1, this is equivalent to Condorcet winner, which rarely exists. The concept of β-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [SoCG 2020] as a relaxation of the Condorcet criterion. Denote by β*(X,d) the value sup{ β ∣ every finite multiset V in X admits a β-plurality point}}. The parameter β* determines the amount of relaxation required in order to reach a stable decision. Aronov et al. showed that for the Euclidean plane β*(ℝ2,\|⋅\|2)=√3/2 , and more generally, for d-dimensional Euclidean space, 1/√d ≤ β*(ℝd,\|⋅\|2)≤√3/2 . In this paper, we show that 0.557≤ β*(ℝd,\|⋅\|2) for any dimension d (notice that 1/√d

In network design problems, such as compact routing, the goal is to route packets between nodes using the (approximated) shortest paths. A desirable property of these routes is a small number of hops, which makes them more reliable, and reduces the transmission costs. Following the overwhelming success of stochastic tree embeddings for algorithmic design, Haeupler, Hershkowitz, and Zuzic (STOC'21) studied hop-constrained Ramsey-type metric embeddings into trees. Specifically, embedding$f: G(V, E)\rightarrow T$has Ramsey hop-distortion ($t, M,\beta, h$), (here$t, \beta, h\geq 1$and$M\subseteq V)$if$\forall u\in M, v\in V,\ d_{G}^{(\beta\cdot h)}(u, v)\leq d_{T}(u, v)\leq t\cdot d_{G}^{(h)}(u, v). t$is called the distortion,$\beta$is called the hop-stretch, and$d_{G}^{(h)}(u, v)$denotes the minimum weight of a$u-v$path with at most$h$hops. Haeupler et al. constructed embedding where$M$contains$1-\epsilon$fraction of the vertices and$\beta=t=O(\frac{\log^{2}n}{\epsilon})$. They used their embedding to obtain multiple bicriteria approximation algorithms for hop-constrained network design problems. In this paper, we first improve the Ramsey-type embedding to obtain parameters$t=\beta=\frac{\tilde{O}(\log n)}{\epsilon}$, and generalize it to arbitrary distortion parameter$t$(in the cost of reducing the size of$M$). This embedding immediately implies polynomial improvements for all the approximation algorithms from Haeupler et al.. Further, we construct hop-constrained clan embeddings (where each vertex has multiple copies), and use them to construct bicriteria approximation algorithms for the group Steiner tree problem, matching the state of the art of the non constrained version. Finally, we use our embedding results to construct hop constrained distance oracles, distance labeling, and most prominently, the first hop constrained compact routing scheme with provable guarantees. All our metric data structures almost match the state of the art parameters of the non-constrained versions.

Given a curve P with points in ℝd in a streaming fashion, and parameters ∊ > 0 and k, we construct a distance oracle that uses space, and given a query curve Q with k points in ℝd, returns in O(kd) time a 1 + ∊ approximation of the discrete Fréchet distance between Q and P. In addition, we construct simplifications in the streaming model, oracle for distance queries to a sub-curve (in the static setting), and introduce the zoom-in problem. Our algorithms work in any dimension d, and therefore we generalize some useful tools and algorithms for curves under the discrete Fréchet distance to work efficiently in high dimensions.

Graph sketching is a powerful technique introduced by the seminal work of Ahn, Guha and McGregor'12 on connectivity in dynamic graph streams that has enjoyed considerable attention in the literature since then, and has led to near optimal dynamic streaming algorithms for many fundamental problems such as connectivity, cut and spectral sparsifiers and matchings. Interestingly, however, the sketching and dynamic streaming complexity of approximating the shortest path metric of a graph is still far from well-understood. Besides a direct k-pass implementation of classical spanner constructions (recently improved to -passes by Fernandez, Woodruff and Yasuda'20) the state of the art amounts to a O(log k)-pass algorithm of Ahn, Guha and McGregor'12, and a 2-pass algorithm of Kapralov and Woodruff'14. In particular, no single pass algorithm is known, and the optimal tradeoff between the number of passes, stretch and space complexity is open. In this paper we introduce several new graph sketching techniques for approximating the shortest path metric of the input graph. We give the first single pass sketching algorithm for constructing graph spanners: we show how to obtain a Õ(n⅔)-spanner using Õ(n) space, and in general a Õ(n⅔(1–α))-spanner using Õ(n1+α) space for every α ∊ [0, 1], a tradeoff that we think may be close optimal. We also give new spanner construction algorithms for any number of passes, simultaneously improving upon all prior work on this problem. Finally, we note that unlike the original sketching approach of Ahn, Guha and McGregor'12, none of the existing spanner constructions yield simultaneous communication protocols with low per player information. We give the first such protocols for the spanner problem that use a small number of rounds.

In low distortion metric embeddings, the goal is to embed a host “hard” metric space into a “simpler” target space while approximately preserving pairwise distances. A highly desirable target space is that of a tree metric. Unfortunately, such embedding will result in a huge distortion. A celebrated bypass to this problem is stochastic embedding with logarithmic expected distortion. Another bypass is Ramsey-type embedding, where the distortion guarantee applies only to a subset of the points. However, both these solutions fail to provide an embedding into a single tree with a worst-case distortion guarantee on all pairs. In this paper, we propose a novel third bypass called clan embedding. Here each point x is mapped to a subset of points f(x), called a clan, with a special chief point χ(x)∈ f(x). The clan embedding has multiplicative distortion t if for every pair (x,y) some copy y′∈ f(y) in the clan of y is close to the chief of x: miny′∈ f(y)d(y′,χ(x))≤ t· d(x,y). Our first result is a clan embedding into a tree with multiplicative distortion O(logn/є) such that each point has 1+є copies (in expectation). In addition, we provide a “spanning” version of this theorem for graphs and use it to devise the first compact routing scheme with constant size routing tables.

Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ε, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ε factor, of total weight at most Oε(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion εD. Namely, given a minor-free graph G = (V, E, w) of diameter D, and parameter ε, we construct a distribution D over dominating metric embeddings into treewidth- Oε(logn) graphs such that ∀u, v ∈ V, \mathbbEf ~ D[dH(f(u), f(v))] ≤ dG(u, v)+εD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth).

A partition $\mathcal{P}$ of a weighted graph $G$ is $(σ,τ,Δ)$-sparse if every cluster has diameter at most $Δ$, and every ball of radius $Δ/σ$ intersects at most $τ$ clusters. Similarly, $\mathcal{P}$ is $(σ,τ,Δ)$-scattering if instead for balls we require that every shortest path of length at most $Δ/σ$ intersects at most $τ$ clusters. Given a graph $G$ that admits a $(σ,τ,Δ)$-sparse partition for all $Δ>0$, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch $O(τσ^2\log_τn)$. Given a graph $G$ that admits a $(σ,τ,Δ)$-scattering partition for all $Δ>0$, we construct a solution for the Steiner Point Removal problem with stretch $O(τ^3σ^3)$. We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.

In the (1+ε,r)-approximate near-neighbor problem for curves (ANNC) under some similarity measure δ, the goal is to construct a data structure for a given set 𝒞 of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C ∈ 𝒞 such that δ(Q,C)≤ r, then return a curve C' ∈ 𝒞 with δ(Q,C') ≤ (1+ε)r. There exists an efficient reduction from the (1+ε)-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C ∈ 𝒞 with δ(Q,C) ≤ (1+ε)⋅δ(Q,C^*), where C^* is the curve of 𝒞 most similar to Q. Given a set 𝒞 of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n⋅ O(1/ε)^{md} storage space and has O(md) query time (for a query curve of length m), where the similarity measure between two curves is their discrete Fréchet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds. Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k ≪ m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds.

A t-spanner H of a weighted graph G = (V, E, w) is a subgraph that approximates all pairwise distances up to a factor of t. The lightness of H is defined as the ratio between the weight of H to that of the minimum spanning tree. An (α, β)-Shallow Light Tree (SLT) is a tree of lightness β, that approximates all distances from a designated root vertex up to a factor of α. A long line of works resulted in efficient algorithms that produce (nearly) optimal light spanners and SLTs.

It was conjectured by Gupta et al. [Combinatorica04] that every planar graph can be embedded into ℓ1 with constant distortion. However, given an n-vertex weighted planar graph, the best upper bound on the distortion is only , by Rao [SoCG99]. In this paper we study the case where there is a set K of terminals, and the goal is to embed only the terminals into ℓ1 with low distortion. In a seminal paper, Okamura and Seymour [J.Comb.Theory81] showed that if all the terminals lie on a single face, they can be embedded isometrically into ℓ1. The more general case, where the set of terminals can be covered by γ faces, was studied by Lee and Sidiropoulos [STOC09] and Chekuri et al. [J.Comb.Theory13]. The state of the art is an upper bound of O(log γ) by Krauthgamer, Lee and Rika [SODA19]. Our contribution is a further improvement on the upper bound to . Since every planar graph has at most O(n) faces, any further improvement on this result, will be a major breakthrough, directly improving upon Rao's long standing upper bound. Moreover, it is well known that the flow-cut gap equals to the distortion of the best embedding into ℓ1. Therefore, our result provides a polynomial time -approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by γ faces.

We investigate for which metric spaces the performance of distance labeling and of ℓ∞-embeddings differ, and how significant can this difference be. Recall that a distance labeling is a distributed representation of distances in a metric space (X, d), where each point x ∊ X is assigned a succinct label, such that the distance between any two points x, y ∊ X can be approximated given only their labels. A highly structured special case is an embedding into ℓ∞, where each point x ∊ X is assigned a vector f (x) such that ‖f(x)−f (y)‖∞ is approximately d(x, y). The performance of a distance labeling or an ℓ∞-embedding is measured via its distortion and its label-size/dimension. We also study the analogous question for the prioritized versions of these two measures. Here, a priority order π = (x1, …, xn) of the point set X is given, and higher-priority points should have shorter labels. Formally, a distance labeling has prioritized label-size α(.) if every xj has label size at most α(j). Similarly, an embedding f: X → ℓ∞ has prioritized dimension α(·) if f (xj) is non-zero only in the first α(j) coordinates. In addition, we compare these their prioritized measures to their classical (worst-case) versions. We answer these questions in several scenarios, uncovering a surprisingly diverse range of behaviors. First, in some cases labelings and embeddings have very similar worst-case performance, but in other cases there is a huge disparity. However in the prioritized setting, we most often find a strict separation between the performance of labelings and embeddings. And finally, when comparing the classical and prioritized settings, we find that the worst-case bound for label size often “translates” to a prioritized one, but also a surprising exception to this rule.

The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is existentially optimal (or existentially near-optimal) for several important graph families in terms of both size and weight. Roughly speaking, the greedy spanner is said to be existentially optimal (or near-optimal) for a graph family $\mathcal G$ if the worst performance of the greedy spanner over all graphs in $\mathcal G$ is just as good (or nearly as good) as the worst performance of an optimal spanner over all graphs in $\mathcal G$. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [ ACM Trans. Algorithms, 14 (2018), 33]) and doubling metrics (due to Gottlieb [ Proceedings of the $56$th Annual IEEE Symposium on Foundations of Computer Science, 2015, pp. 759--772]) are complex. Plugging our observation into these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy spanners are existentially near-optimal as well. Consequently, we provide an $O(n \log n)$-time construction of $(1+\epsilon)$-spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is $O(n \log^2 n)$ and whose number of edges and degree are unbounded, and, remarkably, it matches the state-of-the-art Euclidean result (due to Gudmundsson, Levcopoulos, and Narasimhan [ SIAM J. Comput., 31 (2002), pp. 1479--1500]) in all of the involved parameters (up to dependencies on $\epsilon$ and the dimension).

Given a weighted graph $G=(V,E,w)$, a partition of $V$ is $Δ$-bounded if the diameter of each cluster is bounded by $Δ$. A distribution over $Δ$-bounded partitions is a $β$-padded decomposition if every ball of radius $γΔ$ is contained in a single cluster with probability at least $e^{-β\cdotγ}$. The weak diameter of a cluster $C$ is measured w.r.t. distances in $G$, while the strong diameter is measured w.r.t. distances in the induced graph $G[C]$. The decomposition is weak/strong according to the diameter guarantee. Formerly, it was proven that $K_r$ minor free graphs admit weak decompositions with padding parameter $O(r)$, while for strong decompositions only $O(r^2)$ padding parameter was known. Furthermore, for the case of a graph $G$, for which the induced shortest path metric $d_G$ has doubling dimension $d$, a weak $O(d)$-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known. We construct strong $O(r)$-padded decompositions for $K_r$ minor free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension $d$ we construct a strong $O(d)$-padded decomposition, which is also tight. We use this decomposition to construct strong $\left(O(d),\tilde{O}(d)\right)$ sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.

Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [Shiri Chechik and Christian Wulff-Nilsen, 2018] improved the state-of-the-art for light spanners by constructing a (2k-1)(1+epsilon)-spanner with O(n^(1+1/k)) edges and O_epsilon(n^(1/k)) lightness. Soon after, Filtser and Solomon [Arnold Filtser and Shay Solomon, 2016] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O(mn^(1+1/k)) (which is faster than [Shiri Chechik and Christian Wulff-Nilsen, 2018]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Omega_epsilon(kn^(1/k)), even when randomization is used. The contribution of this paper is deterministic spanner constructions that are fast, and achieve similar bounds as the state-of-the-art slower constructions. Our first result is an O_epsilon(n^(2+1/k+epsilon')) time spanner construction which achieves the state-of-the-art bounds. Our second result is an O_epsilon(m + n log n) time construction of a spanner with (2k-1)(1+epsilon) stretch, O(log k * n^(1+1/k) edges and O_epsilon(log k * n^(1/k)) lightness. This is an exponential improvement in the dependence on k compared to the previous result with such running time. Finally, for the important special case where k=log n, for every constant epsilon>0, we provide an O(m+n^(1+epsilon)) time construction that produces an O(log n)-spanner with O(n) edges and O(1) lightness which is asymptotically optimal. This is the first known sub-quadratic construction of such a spanner for any k = omega(1). To achieve our constructions, we show a novel deterministic incremental approximate distance oracle. Our new oracle is crucial in our construction, as known randomized dynamic oracles require the assumption of a non-adaptive adversary. This is a strong assumption, which has seen recent attention in prolific venues. Our new oracle allows the order of the edge insertions to not be fixed in advance, which is critical as our spanner algorithm chooses which edges to insert based on the answers to distance queries. We believe our new oracle is of independent interest.

In the Steiner point removal problem, we are given a weighted graph $G=(V,E)$ and a set of terminals $K\subset V$ of size $k$. The objective is to find a minor $M$ of $G$ with only the terminals as its vertex set, such that distances between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer, and Nguyen [ SIAM J. Comput., 44 (2015), pp. 975--995] devised a ball-growing algorithm with exponential distributions to show that the distortion is at most $O(\log^5 k)$. Cheung [ Proceedings of the 29th Annual ACM/SIAM Symposium on Discrete Algorithms, 2018, pp. 1353--1360] improved the analysis of the same algorithm, bounding the distortion by $O(\log^2 k)$. We devise a novel and simpler algorithm (called the Relaxed-Voronoi algorithm) which incurs distortion $O(\log k)$. This algorithm can be implemented in almost linear time ($O(|E|\log |V|)$).

The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [MN07] devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S ⊆ V of a given graph G = (V, E), such that there exists a spanning tree of G that has small stretch for S. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees serves as a special type of spanner, a tree-padding spanner. We use this spanner to devise the first compact stateless routing scheme with O(1) routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every k, any n-point metric space has a subset S of size at least n1–1/k which embeds into an ultrametric with distortion 8k. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every k, any n-vertex graph G = (V, E) has a subset S of size at least n1–1/k, and a spanning tree of G, that has stretch O(k log log n) between any point in S and any point in V.

In the Steiner point removal (SPR) problem, we are given a weighted graph G = (V, E) and a set of terminals K ⊂ V of size k. The objective is to find a minor M of G with only the terminals as its vertex set, such that the distance between the terminals will be preserved up to a small multiplicative distortion. Kamma, Krauthgamer and Nguyen [KKN15] used a ball-growing algorithm with exponential distributions to show that the distortion is at most O(log5 k). Cheung [Che18] improved the analysis of the same algorithm, bounding the distortion by O(log2 k). We improve the analysis of this ball-growing algorithm even further, bounding the distortion by O(log k).

We study the problem of embedding weighted graphs of pathwidth k into ℓp spaces. Our main result is an O(kmin{1p,12})-distortion embedding. For p=1, this is a super-exponential improvement over the best previous bound of Lee and Sidiropoulos. Our distortion bound is asymptotically tight for any fixed p >1.

Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215--245], online algorithms [N. Bansal et al., Proceedings of the 52th Annual IEEE Symposium on Foundations of Computer Science, FOCS '08, IEEE Computer Society, Washington, DC, 2011, pp. 267--276], distributed algorithms [M. Khan et al., Distrib. Comput., 25 (2012), pp. 189--205], and for computing sparsifiers [Y. Shavitt and T. Tankel, IEEE/ACM Trans. Netw., 12 (2004), pp. 993--1006]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee. In this paper we alleviate this limitation by devising a suite of prioritized metric data structures and embeddings. We show that given a priority ranking $(x_1,x_2,\ldots,x_n)$ of the graph vertices (resp., metric points) one can devise a metric data structure (resp., embedding) in which the stretch (resp., distortion) incurred by any pair containing a vertex $x_j$ will depend on the rank $j$ of the vertex. We also show that other important parameters, such as the label size and (in some sense) the dimension, may depend only on $j$. In some of our metric data structures (resp., embeddings) we achieve both prioritized stretch (resp., distortion) and label size (resp., dimension) simultaneously. The worst-case performance of our metric data structures and embeddings is typically asymptotically no worse than of their nonprioritized counterparts.

A valued constraint satisfaction problem (VCSP) instance $(V,\Pi,w)$ is a set of variables $V$ with a set of constraints $\Pi$ weighted by $w$. Given a VCSP instance, we are interested in a reweighted subinstance $(V,\Pi'\subset \Pi,w')$ that preserves the value of the given instance (under every assignment to the variables) within factor $1\pm\epsilon$. A well-studied special case is cut sparsification in graphs, which has found various applications. We show that a VCSP instance consisting of a single boolean predicate $P(x,y)$ (e.g., for cut, $P=\mathsf{XOR}$) can be sparsified into $O(|V|/\epsilon^2)$ constraints iff the number of inputs that satisfy $P$ is anything but one (i.e., $|P^{-1}(1)| \neq 1$). Furthermore, this sparsity bound is tight unless $P$ is a relatively trivial predicate. We conclude that also systems of 2SAT (or 2LIN) constraints can be sparsified.

In this paper we study terminal embeddings , in which one is given a finite metric ( X , d X ) (or a graph G = ( V , E ) ) and a subset K ⊆ X of its points are designated as terminals . The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve ≈ | K | ⋅ | X | pairs, the distortion depends only on | K | , rather than on | X | . We also strengthen this notion, and consider embeddings that approximately preserve the distances between all pairs, but provide improved distortion for pairs containing a terminal. Surprisingly, we show that such embeddings exist in many settings, and have optimal distortion bounds both with respect to X × X and with respect to K × X . Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [10] devised an O ˜ ( log ⁡ r ) -approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an O ˜ ( log ⁡ | K | ) - approximation for sparsest-cut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since | K | ≤ r , our bound generalizes that of [10] .

The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction, in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is existentially optimal (or existentially near-optimal) for several important graph families. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [SODA'16]) and doubling metrics (due to Gottlieb [FOCS'15]) are complex. Plugging our observation on these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy algorithms are existentially near-optimal as well. Consequently, we provide an O(n log n)-time construction of (1+epsilon)-spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is O(n log2 n) and whose number of edges and degree are unbounded, and remarkably, it matches the state-of-the-art Euclidean result (due to Gudmundsson et al. [SICOMP'02]) in all the involved parameters (up to dependencies on epsilon and the dimension).

Minimum Spanning Trees of weighted graphs are fundamental objects in numerous applications. In particular in distributed networks, the minimum spanning tree of the network is often used to route messages between network nodes. Unfortunately, while being most efficient in the total cost of connecting all nodes, minimum spanning trees fail miserably in the desired property of approximately preserving distances between pairs. While known lower bounds exclude the possibility of the worst case distortion of a tree being small, it was shown in [4] that there exists a spanning tree with constant average distortion. Yet, the weight of such a tree may be significantly larger than that of the MST. In this paper, we show that any weighted undirected graph admits a spanning tree whose weight is at most (1 + ρ) times that of the MST, providing constant average distortion O(1/ρ2).1 The constant average distortion bound is implied by a stronger property of scaling distortion, i.e., improved distortion for smaller fractions of the pairs. The result is achieved by first showing the existence of a low weight spanner with small prioritized distortion, a property allowing to prioritize the nodes whose associated distortions will be improved. We show that prioritized distortion is essentially equivalent to coarse scaling distortion via a general transformation, which has further implications and may be of independent interest. In particular, we obtain an embedding for arbitrary metrics into Euclidean space with optimal prioritized distortion.

Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms [21], online algorithms [7], distributed algorithms [19] and for computing sparsifiers [28]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee.

Determining whether an unordered collection of overlapping substrings (called shingles) can be uniquely decoded into a consistent string is a problem common to a broad assortment of disciplines ranging from networking and information theory through cryptography and even genetic engineering and linguistics. We present a new insight that yields an efficient streaming algorithm for determining whether a string of n characters over the alphabet Σ can be uniquely decoded from its two-character shingles; our online algorithm achieves an overall time complexity Θ(n+|Σ|) and space complexity O(|Σ|). As a motivating application, we demonstrate how this algorithm can be adapted to larger, varying-size shingles for (empirically) efficient string reconciliation.