Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Euclidean Steiner $(1+epsilon)$-Spanners
99
0
0.0
(
0
)
Added by
Csaba D. Toth
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Lightness and sparsity are two natural parameters for Euclidean $(1+varepsilon)$-spanners. Classical results show that, when the dimension $din mathbb{N}$ and $varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+varepsilon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $varepsilon>0$ for constant $din mathbb{N}$ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a $(1+varepsilon)$-spanner. They gave upper bounds of $tilde{O}(varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $dgeq 3$, and $tilde{O}(varepsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $dgeq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltain Omega(sqrt{n})$ is the emph{spread} of $S$, defined as the ratio between the maximum and minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner $(1+varepsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Omega(varepsilon^{-d/2})$ for the lightness and $Omega(varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $dgeq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}log n)$ for $n$ points in Euclidean plane.
rate research
Read More
Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in $mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on $varepsilon>0$ and $din mathbb{N}$ of the minimum lightness of $(1+varepsilon)$-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner $(1+varepsilon)$-spanners of lightness $O(varepsilon^{-1}logDelta)$ in the plane, where $Deltageq Omega(sqrt{n})$ is the emph{spread} of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness $tilde{O}(varepsilon^{-(d+1)/2})$ in dimensions $dgeq 3$. Recently, Bhore and T{o}th (2020) established a lower bound of $Omega(varepsilon^{-d/2})$ for the lightness of Steiner $(1+varepsilon)$-spanners in $mathbb{R}^d$, for $dge 2$. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions $dgeq 2$. In this work, we show that for every finite set of points in the plane and every $varepsilon>0$, there exists a Euclidean Steiner $(1+varepsilon)$-spanner of lightness $O(varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.
In this paper, we study the online Euclidean spanners problem for points in $mathbb{R}^d$. Suppose we are given a sequence of $n$ points $(s_1,s_2,ldots, s_n)$ in $mathbb{R}^d$, where point $s_i$ is presented in step~$i$ for $i=1,ldots, n$. The objective of an online algorithm is to maintain a geometric $t$-spanner on $S_i={s_1,ldots, s_i}$ for each step~$i$. First, we establish a lower bound of $Omega(varepsilon^{-1}log n / log varepsilon^{-1})$ for the competitive ratio of any online $(1+varepsilon)$-spanner algorithm, for a sequence of $n$ points in 1-dimension. We show that this bound is tight, and there is an online algorithm that can maintain a $(1+varepsilon)$-spanner with competitive ratio $O(varepsilon^{-1}log n / log varepsilon^{-1})$. Next, we design online algorithms for sequences of points in $mathbb{R}^d$, for any constant $dge 2$, under the $L_2$ norm. We show that previously known incremental algorithms achieve a competitive ratio $O(varepsilon^{-(d+1)}log n)$. However, if the algorithm is allowed to use additional points (Steiner points), then it is possible to substantially improve the competitive ratio in terms of $varepsilon$. We describe an online Steiner $(1+varepsilon)$-spanner algorithm with competitive ratio $O(varepsilon^{(1-d)/2} log n)$. As a counterpart, we show that the dependence on $n$ cannot be eliminated in dimensions $d ge 2$. In particular, we prove that any online spanner algorithm for a sequence of $n$ points in $mathbb{R}^d$ under the $L_2$ norm has competitive ratio $Omega(f(n))$, where $lim_{nrightarrow infty}f(n)=infty$. Finally, we provide improved lower bounds under the $L_1$ norm: $Omega(varepsilon^{-2}/log varepsilon^{-1})$ in the plane and $Omega(varepsilon^{-d})$ in $mathbb{R}^d$ for $dgeq 3$.
Given two sets of points in the plane, $P$ of $n$ terminals and $S$ of $m$ Steiner points, a Steiner tree of $P$ is a tree spanning all points of $P$ and some (or none or all) points of $S$. A Steiner tree with length of longest edge minimized is called a bottleneck Steiner tree. In this paper, we study the Euclidean bottleneck Steiner tree problem: given two sets, $P$ and $S$, and a positive integer $k le m$, find a bottleneck Steiner tree of $P$ with at most $k$ Steiner points. The problem has application in the design of wireless communication networks. We first show that the problem is NP-hard and cannot be approximated within factor $sqrt{2}$, unless $P=NP$. Then, we present a polynomial-time approximation algorithm with performance ratio 2.
We present online algorithms for directed spanners and Steiner forests. These problems fall under the unifying framework of online covering linear programming formulations, developed by Buchbinder and Naor (MOR, 34, 2009), based on primal-dual techniques. Our results include the following: For the pairwise spanner problem, in which the pairs of vertices to be spanned arrive online, we present an efficient randomized $tilde{O}(n^{4/5})$-competitive algorithm for graphs with general lengths, where $n$ is the number of vertices. With uniform lengths, we give an efficient randomized $tilde{O}(n^{2/3+epsilon})$-competitive algorithm, and an efficient deterministic $tilde{O}(k^{1/2+epsilon})$-competitive algorithm, where $k$ is the number of terminal pairs. These are the first online algorithms for directed spanners. In the offline setting, the current best approximation ratio with uniform lengths is $tilde{O}(n^{3/5 + epsilon})$, due to Chlamtac, Dinitz, Kortsarz, and Laekhanukit (TALG 2020). For the directed Steiner forest problem with uniform costs, in which the pairs of vertices to be connected arrive online, we present an efficient randomized $tilde{O}(n^{2/3 + epsilon})$-competitive algorithm. The state-of-the-art online algorithm for general costs is due to Chakrabarty, Ene, Krishnaswamy, and Panigrahi (SICOMP 2018) and is $tilde{O}(k^{1/2 + epsilon})$-competitive. In the offline version, the current best approximation ratio with uniform costs is $tilde{O}(n^{26/45 + epsilon})$, due to Abboud and Bodwin (SODA 2018). A small modification of the online covering framework by Buchbinder and Naor implies a polynomial-time primal-dual approach with separation oracles, which a priori might perform exponentially many calls. We convert the online spanner problem and the online Steiner forest problem into online covering problems and round in a problem-specific fashion.
In this thesis, we study two different graph problems. The first problem revolves around geometric spanners. Here, we have a set of points in the plane and we want to connect them with straight line segments, such that there is a path between each pair of points that does not make a large detour. If we achieve this, the resulting graph is called a spanner. We focus our attention on $Theta$-graphs, which are constructed by connecting each point with its nearest neighbour in a fixed number of cones. Although this construction is very straight-forward, it has proven challenging to fully determine the properties of the resulting graphs. We show that if the construction uses 5 cones, the resulting graphs are still spanners. This was the only number of cones for which this question remained unanswered. We also present a routing strategy on the half-$Theta_6$-graph, a variant of the graph with 6 cones. We show that our routing strategy finds a path whose length is at most a constant factor from the straight-line distance between the endpoints. Moreover, we show that this routing strategy is optimal. In the second part, we turn our attention to flips in triangulations. A flip is a simple operation that transforms one triangulation into another. It turns out that with enough flips, we can transform any triangulation into any other. But how many flips is enough? We present an improved upper bound of $5.2n - 33.6$ on the maximum flip distance between any pair of triangulations with n vertices. Along the way, we prove matching lower bounds on each step in the current algorithm, including a tight bound of $(3n - 9)/5$ flips needed to make a triangulation 4-connected. In addition, we prove tight $Theta(n log n)$ bounds on the number of flips required in several settings where the edges have unique labels.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
