Source author record

Arnold Filtser

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

On Strong Diameter Padded Decompositions

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.

preprint2023arXiv

Metric Embedding via Shortest Path Decompositions

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 depth is inductively defined: A (weighed) path graph has shortest path decomposition (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\{\frac{1}{p},\frac{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\{\frac{1}{p},\frac{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.

preprint2022arXiv

Approximate Nearest Neighbor for Curves: Simple, Efficient, and Deterministic

In the $(1+\varepsilon,r)$ -approximate near-neighbor problem for curves (ANNC) under some distance measure $δ$ , the goal is to construct a data structure for a given set $\mathcal{C}$ of curves that supports approximate near-neighbor queries: Given a query curve $Q$ , if there exists a curve $C\in\mathcal{C}$ such that $δ(Q,C)\le r$ , then return a curve $C'\in\mathcal{C}$ with $δ(Q,C')\le(1+\varepsilon)r$ . There exists an efficient reduction from the $(1+\varepsilon)$ -approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve $C\in\mathcal{C}$ with $δ(Q,C)\le(1+\varepsilon)\cdotδ(Q,C^*)$ , where $C^*$ is the curve of $\mathcal{C}$ closest to $Q$ . Given a set $\mathcal{C}$ of $n$ curves, each consisting of $m$ points in $d$ dimensions, we construct a data structure for ANNC that uses $n\cdot O(\frac{1}{\varepsilon})^{md}$ storage space and has $O(md)$ query time (for a query curve of length $m$ ), where the similarity 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 \ll 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.

preprint2022arXiv

Constructing Light Spanners Deterministically in Near-Linear Time

Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [CW18] improved the state-of-the-art for light spanners by constructing a $(2k-1)(1+ε)$ -spanner with $O(n^{1+1/k})$ edges and $O_ε(n^{1/k})$ lightness. Soon after, Filtser and Solomon [FS19] 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 [CW16]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness $Ω_ε(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_ε(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 $(2k-1)(1+ε)$ stretch, $O(\log k\cdot n^{1+1/k})$ edges and $O_ε(\log k\cdot 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, which may be of independent interest.

preprint2022arXiv

Locality-Sensitive Orderings and Applications to Reliable Spanners

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 $\mathbb{R}^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 {\em et al. } to construct very sparse \emph{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 $\tilde{O}(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.

preprint2022arXiv

Low Treewidth Embeddings of Planar and Minor-Free Metrics

Cohen-Addad, Filtser, Klein and Le [FOCS'20] constructed a stochastic embedding of minor-free graphs of diameter $D$ into graphs of treewidth $O_ε(\log n)$ with expected additive distortion $+ε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_ε(\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_ε(\log(n))}$ to $n^{O_ε(\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 $O((\log\log n)^2)/ε)$ and additive distortion $+ε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.

preprint2020arXiv

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

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 subgraph 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 $\mathcal{D}$ over dominating metric embeddings into treewidth- $O_ε(\log n)$ graphs such that the additive distortion is at most $εD$ . One of our important technical contributions is a novel framework that allows us to reduce \emph{both problems} to problems on simpler graphs of bounded diameter. 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 vehicle routing with bounded capacity in minor-free metrics; (3) the first efficient approximation scheme for vehicle routing with bounded capacity on bounded genus metrics.

preprint2020arXiv

Static and Streaming Data Structures for Fréchet Distance Queries

Given a curve $P$ with points in $\mathbb{R}^d$ in a streaming fashion, and parameters $\varepsilon>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 $\mathbb{R}^d$ , returns in $\tilde{O}(kd)$ time a $1+\varepsilon$ 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.

preprint2020arXiv

The Greedy Spanner is Existentially Optimal

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 \emph{existentially optimal} (or existentially near-optimal) for several important graph families, in terms of both the 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 [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 spanners are existentially near-optimal as well. Consequently, we provide an $O(n \log n)$ -time construction of $(1+ε)$ -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 et al.\ [SICOMP'02]) in all the involved parameters (up to dependencies on $ε$ and the dimension).

preprint2016arXiv

Terminal Embeddings

In this paper we study {\em terminal embeddings}, in which one is given a finite metric $(X,d_X)$ (or a graph $G=(V,E)$ ) and a subset $K \subseteq X$ of its points are designated as {\em 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 $\approx|K|\cdot |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 {\em 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 \times X$ and with respect to $K \times X$ . Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [ALN08] devised an $\tilde{O}(\sqrt{\log r})$ -approximation algorithm for sparsest-cut instances with $r$ demands. Building on their framework, we provide an $\tilde{O}(\sqrt{\log |K|})$ -approximation for sparsest-cut instances in which each demand is incident on one of the vertices of $K$ (aka, terminals). Since $|K| \le r$ , our bound generalizes that of [ALN08].

preprint2015arXiv

Prioritized Metric Structures and Embedding

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 \cite{llr}, online algorithms \cite{BBMN11}, distributed algorithms \cite{KKMPT12} and for computing sparsifiers \cite{ST04}. 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 suit of {\em prioritized} metric data structures and embeddings. We show that given a priority ranking $(x_1,x_2,\ldots,x_n)$ of the graph vertices (respectively, metric points) one can devise a metric data structure (respectively, 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) {\em simultaneously}. The worst-case performance of our metric data structures and embeddings is typically asymptotically no worse than of their non-prioritized counterparts.

preprint2015arXiv

Sparsification of Two-Variable Valued CSPs

A valued constraint satisfaction problem (VCSP) instance $(V,Π,w)$ is a set of variables $V$ with a set of constraints $Π$ weighted by $w$ . Given a VCSP instance, we are interested in a re-weighted sub-instance $(V,Π'\subset Π,w')$ such that preserves the value of the given instance (under every assignment to the variables) within factor $1\pmε$ . 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=\mbox{XOR}$) can be sparsified into $O(|V|/ε^2)$ constraints if and only if 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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Arnold Filtser

Research overview

Is this your work?

12 publications

On Strong Diameter Padded Decompositions

Metric Embedding via Shortest Path Decompositions

Approximate Nearest Neighbor for Curves: Simple, Efficient, and Deterministic

Constructing Light Spanners Deterministically in Near-Linear Time

Locality-Sensitive Orderings and Applications to Reliable Spanners

Low Treewidth Embeddings of Planar and Minor-Free Metrics

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

Static and Streaming Data Structures for Fréchet Distance Queries

The Greedy Spanner is Existentially Optimal

Terminal Embeddings

Prioritized Metric Structures and Embedding

Sparsification of Two-Variable Valued CSPs

See the researcher in context

Building this map preview