Source author record

Yuval Gitlitz

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

Catalog footprint

Research overview

2works

1topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Almost Shortest Paths with Near-Additive Error in Weighted Graphs

Let $G=(V,E,w)$ be a weighted undirected graph with $n$ vertices and $m$ edges, and fix a set of $s$ sources $S\subseteq V$ . We study the problem of computing {\em almost shortest paths} (ASP) for all pairs in $S \times 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$ . 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^ω\})$ . 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) \in S\times V$ , it provides a path of length $\hat{d}(s,v)$ that satisfies $\hat{d}(s,v) \le (1+ε)d_G(s,v) + β\cdot 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 {\em local} maximum edge weight, as opposed to the global maximum edge weight in previous works. Finally, our $β= (1/ρ)^{O(1/ρ)}$ . We also extend a centralized algorithm of Dor et al. \cite{DHZ00}. For a parameter $κ= 1,2,\ldots$ , this algorithm provides for {\em unweighted} graphs a purely additive approximation of $2(κ-1)$ for {\em all pairs shortest paths} (APASP) in time $\tilde{O}(n^{2+1/κ})$ . Within the same running time, our algorithm for {\em weighted} graphs provides a purely additive error of $2(κ- 1) W(u,v)$ , for every vertex pair $(u,v) \in {V \choose 2}$ , with $W(u,v)$ defined as above. On the way to these results we devise a suit of novel constructions of spanners, emulators and hopsets.

preprint2021arXiv

Improved Weighted Additive Spanners

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 [ABSKS20] 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. In addition, [ABSKS20] showed an 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+\varepsilon)W$ spanner for weighted graphs with size $O(n^{4/3})$ (for any constant $\varepsilon>0$ ), thus nearly matching the classical +6 spanner of size $O(n^{4/3})$ for unweighted graphs. Furthermore, we show a $+(2+\varepsilon)W$ subsetwise spanner of size $O(n\cdot\sqrt{|S|})$ , improving the $+4W_{max}$ result of [ABSKS20] (that had the same size). We also show a simple randomized algorithm for a $+4W$ emulator of size $\tilde{O}(n^{4/3})$ . In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $+\tilde{O}(\sqrt{n}\cdot W)$ spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of [DHZ00] for unweighted graphs, we devise an efficient randomized algorithm producing a $+2W$ spanner for weighted graphs of size $\tilde{O}(n^{3/2})$ in $\tilde{O}(n^2)$ time.

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.