Arnold Filtser

ICML Conference 2025 Conference Paper

Faster Approximation Algorithms for k-Center via Data Reduction

• Arnold Filtser
• Shaofeng H. -C. Jiang
• Yi Li 0002
• Anurag Murty Naredla
• Ioannis Psarros
• Qiaoyuan Yang
• Qin Zhang 0001

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.

SODA Conference 2025 Conference Paper

Highway Dimension: a Metric View

• Andreas Emil Feldmann
• Arnold Filtser

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 ≈ 4 r 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. We relax the definition of highway dimension by demanding to hit only approximate shortest paths. In addition to generalizing the original definition, this new definition also incorporates all doubling spaces (in particular the grid graph and the Euclidean plane). We then construct a PTAS for TSP under this new definition (improving a QPTAS w. r. t. the original more restrictive definition of Feldmann et. al. (SICOMP 2018)). Finally, we develop a basic metric toolkit for spaces with small highway dimension by constructing padded decompositions, sparse covers/partitions, and tree covers. An abundance of applications follow.

STOC Conference 2025 Conference Paper

How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs

• Jonathan Conroy
• Arnold Filtser

Roughly, a metric space has padding parameter β if for every Δ>0, there is a stochastic decomposition of the metric points into clusters of diameter at most Δ such that every ball of radius γΔ is contained in a single cluster with probability at least e −γβ . The padding parameter is an important characteristic of a metric space with vast algorithmic implications. In this paper we prove that the shortest path metric of every K r -minor-free graph has padding parameter O (log r ), which is also tight. This resolves a long standing open question, and exponentially improves the previous bound. En route to our main result, we construct sparse covers for K r -minor-free graphs with improved parameters, and we prove a general reduction from sparse covers to padded decompositions.

FOCS Conference 2024 Conference Paper

Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs

• Arnold Filtser
• Gramoz Goranci
• Neel Patel
• Maximilian Probst Gutenberg

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].

SODA Conference 2024 Conference Paper

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings

• Sujoy Bhore
• Arnold Filtser
• Csaba D. Tóth

FOCS Conference 2023 Conference Paper

One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree

• Costas Busch
• Da Qi Chen
• Arnold Filtser
• Daniel Hathcock
• D. Ellis Hershkowitz
• Rajmohan Rajaraman

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.

TCS Journal 2022 Journal Article

Constructing light spanners deterministically in near-linear time

• Stephen Alstrup
• Søren Dahlgaard
• Arnold Filtser
• Morten Stöckel
• Christian Wulff-Nilsen

Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [10] improved the state-of-the-art for light spanners by constructing a ( 2 k − 1 ) ( 1 + ε ) -spanner with O ( n 1 + 1 k ) edges and O ε ( n 1 k ) lightness. Soon after, Filtser and Solomon [18] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O ( m n 1 + 1 k ) (which is faster than [10]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Ω ε ( k n 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 ε ( n 2 + 1 k + ε ′ ) time spanner construction which achieves the state-of-the-art bounds. Our second result is an O ε ( m + n log ⁡ n ) time construction of a spanner with ( 2 k − 1 ) ( 1 + ε ) stretch, O ( log ⁡ k ⋅ n 1 + 1 k ) edges and O ε ( 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 ε > 0, we provide an O ( m + n 1 + ε ) 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 = ω ( 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.

STOC Conference 2022 Conference Paper

Locality-sensitive orderings and applications to reliable spanners

• Arnold Filtser
• Hung Le 0001

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. In this paper, we develop the theory of LSO’s in non-Euclidean metrics by introducing new types of LSO’s suitable for general and topologically structured metrics. We then construct such LSO’s, as well as constructing considerably improved LSO’s for doubling metrics. Afterwards, we use our new LSO’s to construct reliable spanners with improved stretch and sparsity parameters. Most prominently, we construct Õ( n )-size reliable spanners for trees and planar graphs with the optimal stretch of 2. Along the way to the construction of LSO’s and reliable spanners, we introduce and construct ultrametric covers, and construct 2-hop reliable spanners for the line.

FOCS Conference 2022 Conference Paper

Low Treewidth Embeddings of Planar and Minor-Free Metrics

• Arnold Filtser
• Hung Le 0001

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.

STOC Conference 2021 Conference Paper

Clan embeddings into trees, and low treewidth graphs

• Arnold Filtser
• Hung Le 0001

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 : min y ′∈ f ( y ) d ( y ′,χ( x ))≤ t · d ( x , y ). Our first result is a clan embedding into a tree with multiplicative distortion O (log n /є) 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.

AAAI Conference 2021 Conference Paper

Condorcet Relaxation In Spatial Voting

• Arnold Filtser
• Omrit Filtser

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” p 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 β∗ (R2, k·k2) = √ 3 2, and more generally, for ddimensional Euclidean space, 1 √ d ≤ β∗ (Rd, k·k2) ≤ √ 3 2. In this paper, we show that 0. 557 ≤ β∗ (Rd, k·k2) for any dimension d (notice that 1 √ d < 0. 557 for any d ≥ 4). In addition, we prove that for every metric space (X, d) it holds that √ 2 − 1 ≤ β∗ (X, d), and show that there exists a metric space for which β∗ (X, d) ≤ 1 2.

SODA Conference 2021 Conference Paper

Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model

• Arnold Filtser
• Michael Kapralov
• Navid Nouri

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 Õ ( n 1+ α ) 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.

FOCS Conference 2021 Conference Paper

Hop-Constrained Metric Embeddings and their Applications

• Arnold Filtser

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.

SODA Conference 2021 Conference Paper

Static and Streaming Data Structures for Fréchet Distance Queries

• Arnold Filtser
• Omrit Filtser

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.

SODA Conference 2020 Conference Paper

A face cover perspective to ℓ 1 embeddings of planar graphs

• Arnold Filtser

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.

SODA Conference 2020 Conference Paper

Labelings vs. Embeddings: On Distributed Representations of Distances

• Arnold Filtser
• Lee-Ad Gottlieb
• Robert Krauthgamer

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 π = ( x 1, …, x n ) 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 x j has label size at most α ( j ). Similarly, an embedding f: X → ℓ ∞ has prioritized dimension α (·) if f ( x j ) 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.

FOCS Conference 2020 Conference Paper

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs

• Vincent Cohen-Addad
• Arnold Filtser
• Philip N. Klein
• Hung Le 0001

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).

AIJ Journal 2019 Journal Article

Distributed monitoring of election winners

• Arnold Filtser
• Nimrod Talmon

We consider distributed elections, where there is a center and k sites. In such distributed elections, each voter has preferences over some set of candidates, and each voter is assigned to exactly one site such that each site is aware only of the voters assigned to it. The center is able to directly communicate with all sites. We are interested in designing communication-efficient protocols, allowing the center to maintain a candidate which, with arbitrarily high probability, is guaranteed to be a winner, or at least close to being a winner. We consider various single-winner voting rules, such as variants of Approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules. For the voting rules we consider, we show that, using communication which is logarithmic in the number of voters, it is possible for the center to maintain such approximate winners; that is, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. We complement our protocols with lower bounds. Our results are theoretical in nature and relate to various scenarios, such as aggregating customer preferences in online shopping websites or supermarket chains and collecting votes from different polling stations of political elections.

STOC Conference 2018 Conference Paper

Metric embedding via shortest path decompositions

• Ittai Abraham
• Arnold Filtser
• Anupam Gupta 0001
• Ofer Neiman

We study the problem of embedding weighted graphs of pathwidth k into ℓ p spaces. Our main result is an O ( k min{1 p ,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.

SODA Conference 2018 Conference Paper

Ramsey Spanning Trees and their Applications

• Ittai Abraham
• Shiri Chechik
• Michael Elkin
• Arnold Filtser
• Ofer Neiman

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 n 1–1/ k which embeds into an ultrametric with distortion 8 k. 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 n 1–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.

SODA Conference 2018 Conference Paper

Steiner Point Removal with Distortion O (log k )

• Arnold Filtser

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 (log 5 k ). Cheung [Che18] improved the analysis of the same algorithm, bounding the distortion by O (log 2 k ). We improve the analysis of this ball-growing algorithm even further, bounding the distortion by O (log k ).

AAMAS Conference 2017 Conference Paper

Distributed Monitoring of Election Winners

• Arnold Filtser
• Nimrod Talmon

We consider distributed elections, where there is a center and k sites. In such distributed elections, each voter has preferences over some set of candidates, and each voter is assigned to exactly one site such that each site is aware only of the voters assigned to it. The center is able to directly communicate with each of the sites. We are interested in designing communication-efficient protocols, allowing the center to maintain (i. e. , declare) a candidate which, with arbitrary high probability, is guaranteed to be a winner, or at least close to being a winner. We consider various single-winner voting rules, such as variants of Approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules. For these voting rules, we show that, using communication which is logarithmic in the number of voters, it is possible for the center to maintain such approximate winners. We complement our protocols with lower bounds. Our results have implications in various scenarios, such as aggregating customer preferences in online shopping websites or supermarket chains and collecting votes from different polling stations of political elections.

TCS Journal 2017 Journal Article

Terminal embeddings

• Michael Elkin
• Arnold Filtser
• Ofer Neiman

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].

SODA Conference 2016 Conference Paper

On Notions of Distortion and an Almost Minimum Spanning Tree with Constant Average Distortion

• Yair Bartal
• Arnold Filtser
• Ofer Neiman

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.

STOC Conference 2015 Conference Paper

Prioritized Metric Structures and Embedding

• Michael Elkin
• Arnold Filtser
• Ofer Neiman

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.