DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.51

(1+ε)-Approximate Shortest Paths in Dynamic Streams

Authors: Michael Elkin and Chhaya Trehan

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract

Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of 2κ-1 versus n^{1+1/κ}, for an integer parameter κ. (In fact, existing solutions also incur an extra factor of 1+ε in the stretch for weighted graphs, and an additional factor of log^{O(1)}n in the space.) The only existing solution of the second type uses n^{1/2 - O(1/κ)} passes over the stream (for space O(n^{1+1/κ})), and applies only to unweighted graphs. In this paper we show that (1+ε)-approximate single-source shortest paths can be computed with Õ(n^{1+1/κ}) space using just constantly many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs. Moreover, the same result applies for multi-source shortest paths, as long as the number of sources is O(n^{1/κ}). We achieve these results by devising efficient dynamic streaming constructions of (1 + ε, β)-spanners and hopsets. On our way to these results, we also devise a new dynamic streaming algorithm for the 1-sparse recovery problem. Even though our algorithm for this task is slightly inferior to the existing algorithms of [S. Ganguly, 2007; Graham Cormode and D. Firmani, 2013], we believe that it is of independent interest.

Cite as

Michael Elkin and Chhaya Trehan. (1+ε)-Approximate Shortest Paths in Dynamic Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 51:1-51:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.APPROX/RANDOM.2022.51,
  author =	{Elkin, Michael and Trehan, Chhaya},
  title =	{{(1+\epsilon)-Approximate Shortest Paths in Dynamic Streams}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{51:1--51:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.51},
  URN =		{urn:nbn:de:0030-drops-171733},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.51},
  annote =	{Keywords: Shortest Paths, Dynamic Streams, Approximate Distances, Spanners, Hopsets}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2022.23

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Authors: Michael Elkin, Yuval Gitlitz, and Ofer Neiman

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract

Let G = (V,E,w) be a weighted undirected graph with n vertices and m edges, and fix a set of s sources S ⊆ V. We study the problem of computing almost shortest paths (ASP) for all pairs in S × V in both classical centralized and parallel (PRAM) models of computation. Consider the regime of multiplicative approximation of 1+ε, for an arbitrarily small constant ε > 0 (henceforth (1+ε)-ASP for S × V). In this regime existing centralized algorithms require Ω(min{|E|s,n^ω}) time, where ω < 2.372 is the matrix multiplication exponent. Existing PRAM algorithms with polylogarithmic depth (aka time) require work Ω(min{|E|s,n^ω}). In a bold attempt to achieve centralized time close to the lower bound of m + n s, Cohen [Edith Cohen, 2000] devised an algorithm which, in addition to the multiplicative stretch of 1+ε, allows also additive error of β ⋅ W_{max}, where W_{max} is the maximum edge weight in G (assuming that the minimum edge weight is 1), and β = (log n)^{O((log 1/ρ)/ρ)} is polylogarithmic in n. It also depends on the (possibly) arbitrarily small parameter ρ > 0 that determines the running time O((m + ns)n^ρ) of the algorithm. The tradeoff of [Edith Cohen, 2000] was improved in [M. Elkin, 2001], whose algorithm has similar approximation guarantee and running time, but its β is (1/ρ)^{O((log 1/ρ)/ρ)}. However, the latter algorithm produces distance estimates rather than actual approximate shortest paths. Also, the additive terms in [Edith Cohen, 2000; M. Elkin, 2001] depend linearly on a possibly quite large global maximum edge weight W_{max}. In the current paper we significantly improve this state of affairs. Our centralized algorithm has running time O((m+ ns)n^ρ), and its PRAM counterpart has polylogarithmic depth and work O((m + ns)n^ρ), for an arbitrarily small constant ρ > 0. For a pair (s,v) ∈ S× V, it provides a path of length d̂(s,v) that satisfies d̂(s,v) ≤ (1+ε)d_G(s,v) + β ⋅ W(s,v), where W(s,v) is the weight of the heaviest edge on some shortest s-v path. Hence our additive term depends linearly on a local maximum edge weight, as opposed to the global maximum edge weight in [Edith Cohen, 2000; M. Elkin, 2001]. Finally, our β = (1/ρ)^{O(1/ρ)}, i.e., it is significantly smaller than in [Edith Cohen, 2000; M. Elkin, 2001]. We also extend a centralized algorithm of Dor et al. [D. Dor et al., 2000]. For a parameter κ = 1,2,…, this algorithm provides for unweighted graphs a purely additive approximation of 2(κ -1) for all pairs shortest paths (APASP) in time Õ(n^{2+1/κ}). Within the same running time, our algorithm for weighted graphs provides a purely additive error of 2(κ - 1) W(u,v), for every vertex pair (u,v) ∈ binom(V,2), with W(u,v) defined as above. On the way to these results we devise a suite of novel constructions of spanners, emulators and hopsets.

Cite as

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Almost Shortest Paths with Near-Additive Error in Weighted Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.SWAT.2022.23,
  author =	{Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer},
  title =	{{Almost Shortest Paths with Near-Additive Error in Weighted Graphs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.23},
  URN =		{urn:nbn:de:0030-drops-161833},
  doi =		{10.4230/LIPIcs.SWAT.2022.23},
  annote =	{Keywords: spanners, hopset, shortest paths, PRAM, distance oracles}
}

Document

DOI: 10.4230/LIPIcs.STACS.2022.27

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Authors: Michael Elkin and Ofer Neiman

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract

Consider an undirected weighted graph G = (V,E,w). We study the problem of computing (1+ε)-approximate shortest paths for S × V, for a subset S ⊆ V of |S| = n^r sources, for some 0 < r ≤ 1. We devise a significantly improved algorithm for this problem in the entire range of parameter r, in both the classical centralized and the parallel (PRAM) models of computation, and in a wide range of r in the distributed (Congested Clique) model. Specifically, our centralized algorithm for this problem requires time Õ(|E| ⋅ n^{o(1)} + n^{ω(r)}), where n^{ω(r)} is the time required to multiply an n^r × n matrix by an n × n one. Our PRAM algorithm has polylogarithmic time (log n)^{O(1/ρ)}, and its work complexity is Õ(|E| ⋅ n^ρ + n^{ω(r)}), for any arbitrarily small constant ρ > 0. In particular, for r ≤ 0.313…, our centralized algorithm computes S × V (1+ε)-approximate shortest paths in n^{2 + o(1)} time. Our PRAM polylogarithmic-time algorithm has work complexity O(|E| ⋅ n^ρ + n^{2+o(1)}), for any arbitrarily small constant ρ > 0. Previously existing solutions either require centralized time/parallel work of O(|E| ⋅ |S|) or provide much weaker approximation guarantees. In the Congested Clique model, our algorithm solves the problem in polylogarithmic time for |S| = n^r sources, for r ≤ 0.655, while previous state-of-the-art algorithms did so only for r ≤ 1/2. Moreover, it improves previous bounds for all r > 1/2. For unweighted graphs, the running time is improved further to poly(log log n) for r ≤ 0.655. Previously this running time was known for r ≤ 1/2.

Cite as

Michael Elkin and Ofer Neiman. Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.STACS.2022.27,
  author =	{Elkin, Michael and Neiman, Ofer},
  title =	{{Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{27:1--27:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.27},
  URN =		{urn:nbn:de:0030-drops-158379},
  doi =		{10.4230/LIPIcs.STACS.2022.27},
  annote =	{Keywords: Shortest paths, matrix multiplication, hopsets}
}

Document

DOI: 10.4230/LIPIcs.DISC.2021.21

Improved Weighted Additive Spanners

Authors: Michael Elkin, Yuval Gitlitz, and Ofer Neiman

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently [Abu Reyan Ahmed et al., 2020] extended the classical +2 (respectively, +4) spanners for unweighted graphs of size O(n^{3/2}) (resp., O(n^{7/5})) to the weighted setting, where the additive error is +2W (resp., +4W). This means that for every pair u,v, the additive stretch is at most +2W_{u,v}, where W_{u,v} is the maximal edge weight on the shortest u-v path (weights are normalized so that the minimum edge weight is 1). In addition, [Abu Reyan Ahmed et al., 2020] showed a randomized algorithm yielding a +8W_{max} spanner of size O(n^{4/3}), here W_{max} is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a +(6+ε)W spanner for weighted graphs with size O(n^{4/3}) (for any constant ε > 0), thus nearly matching the classical +6 spanner of size O(n^{4/3}) for unweighted graphs. Furthermore, we show a +(2+ε)W subsetwise spanner of size O(n⋅√{|S|}), improving the +4W_{max} result of [Abu Reyan Ahmed et al., 2020] (that had the same size). We also show a simple randomized algorithm for a +4W emulator of size Õ(n^{4/3}). In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. It is known that such spanners must suffer polynomially large stretch. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size +Õ(√n⋅ W) spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of [D. Dor et al., 2000] for unweighted graphs, we devise an efficient randomized algorithm producing a +2W spanner for weighted graphs of size Õ(n^{3/2}) in Õ(n²) time.

Cite as

Michael Elkin, Yuval Gitlitz, and Ofer Neiman. Improved Weighted Additive Spanners. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.DISC.2021.21,
  author =	{Elkin, Michael and Gitlitz, Yuval and Neiman, Ofer},
  title =	{{Improved Weighted Additive Spanners}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.21},
  URN =		{urn:nbn:de:0030-drops-148232},
  doi =		{10.4230/LIPIcs.DISC.2021.21},
  annote =	{Keywords: Graph theory, Pure additive spanners}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2018.36

Near Isometric Terminal Embeddings for Doubling Metrics

Authors: Michael Elkin and Ofer Neiman

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

Given a metric space (X,d), a set of terminals K subseteq X, and a parameter t >= 1, we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in K x X up to a factor of t, and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, i.e., t=1+epsilon for some small 0<epsilon<1, is currently known. Here we devise such terminal metric structures for doubling metrics, and show that essentially any metric structure with distortion 1+epsilon and size s(|X|) has its terminal counterpart, with distortion 1+O(epsilon) and size s(|K|)+1. In particular, for any doubling metric on n points, a set of k=o(n) terminals, and constant 0<epsilon<1, there exists - A spanner with stretch 1+epsilon for pairs in K x X, with n+o(n) edges. - A labeling scheme with stretch 1+epsilon for pairs in K x X, with label size ~~ log k. - An embedding into l_infty^d with distortion 1+epsilon for pairs in K x X, where d=O(log k). Moreover, surprisingly, the last two results apply if only K is a doubling metric, while X can be arbitrary.

Cite as

Michael Elkin and Ofer Neiman. Near Isometric Terminal Embeddings for Doubling Metrics. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.SoCG.2018.36,
  author =	{Elkin, Michael and Neiman, Ofer},
  title =	{{Near Isometric Terminal Embeddings for Doubling Metrics}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.36},
  URN =		{urn:nbn:de:0030-drops-87498},
  doi =		{10.4230/LIPIcs.SoCG.2018.36},
  annote =	{Keywords: metric embedding, spanners, doubling metrics}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.242

Terminal Embeddings

Authors: Michael Elkin, Arnold Filtser, and Ofer Neiman

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract

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 of 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 approx |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 \times X and with respect to K * X. Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, Arora et. al. devised an ~O(sqrt(log(r))-approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an ~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| <= r, our bound generalizes that of Arora et al.

Cite as

Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 242-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.APPROX-RANDOM.2015.242,
  author =	{Elkin, Michael and Filtser, Arnold and Neiman, Ofer},
  title =	{{Terminal Embeddings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{242--264},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.242},
  URN =		{urn:nbn:de:0030-drops-53064},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.242},
  annote =	{Keywords: embedding, distortion, terminals}
}

Search Results

Documents authored by Elkin, Michael

(1+ε)-Approximate Shortest Paths in Dynamic Streams

Abstract

Cite as

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Abstract

Cite as

Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Abstract

Cite as

Improved Weighted Additive Spanners

Abstract

Cite as

Near Isometric Terminal Embeddings for Doubling Metrics

Abstract

Cite as

Terminal Embeddings

Abstract

Cite as

Thanks for your feedback!

Could not send message