Arrow Research search

Author name cluster

Arnold Filtser

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

25 papers
2 author rows

Possible papers

25

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.

Details

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.

Details

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.

Details

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

Details

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.

Details

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.

Details

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.

Details

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.

PDF Details

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.

Details

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.

Details

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

Details

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.

Details

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

Details

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.

PDF

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.

Details