Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTime-Space Trade-Offs for Computing Euclidean Minimum Spanning Trees
185
0
0.0
(
0
)
Added by
Bahareh Banyassady
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present time-space trade-offs for computing the Euclidean minimum spanning tree of a set $S$ of $n$ point-sites in the plane. More precisely, we assume that $S$ resides in a random-access memory that can only be read. The edges of the Euclidean minimum spanning tree $text{EMST}(S)$ have to be reported sequentially, and they cannot be accessed or modified afterwards. There is a parameter $s in {1, dots, n}$ so that the algorithm may use $O(s)$ cells of read-write memory (called the workspace) for its computations. Our goal is to find an algorithm that has the best possible running time for any given $s$ between $1$ and $n$. We show how to compute $text{EMST}(S)$ in $Obig((n^3/s^2)log s big)$ time with $O(s)$ cells of workspace, giving a smooth trade-off between the two best known bounds $O(n^3)$ for $s = 1$ and $O(n log n)$ for $s = n$. For this, we run Kruskals algorithm on the relative neighborhood graph (RNG) of $S$. It is a classic fact that the minimum spanning tree of $text{RNG}(S)$ is exactly $text{EMST}(S)$. To implement Kruskals algorithm with $O(s)$ cells of workspace, we define $s$-nets, a compact representation of planar graphs. This allows us to efficiently maintain and update the components of the current minimum spanning forest as the edges are being inserted.
rate research
Read More
In a geometric network G = (S, E), the graph distance between two vertices u, v in S is the length of the shortest path in G connecting u to v. The dilation of G is the maximum factor by which the graph distance of a pair of vertices differs from their Euclidean distance. We show that given a set S of n points with integer coordinates in the plane and a rational dilation delta > 1, it is NP-hard to determine whether a spanning tree of S with dilation at most delta exists.
We revisit the longest common extension (LCE) problem, that is, preprocess a string $T$ into a compact data structure that supports fast LCE queries. An LCE query takes a pair $(i,j)$ of indices in $T$ and returns the length of the longest common prefix of the suffixes of $T$ starting at positions $i$ and $j$. We study the time-space trade-offs for the problem, that is, the space used for the data structure vs. the worst-case time for answering an LCE query. Let $n$ be the length of $T$. Given a parameter $tau$, $1 leq tau leq n$, we show how to achieve either $O(infrac{n}{sqrt{tau}})$ space and $O(tau)$ query time, or $O(infrac{n}{tau})$ space and $O(tau log({|LCE(i,j)|}/{tau}))$ query time, where $|LCE(i,j)|$ denotes the length of the LCE returned by the query. These bounds provide the first smooth trade-offs for the LCE problem and almost match the previously known bounds at the extremes when $tau=1$ or $tau=n$. We apply the result to obtain improved bounds for several applications where the LCE problem is the computational bottleneck, including approximate string matching and computing palindromes. We also present an efficient technique to reduce LCE queries on two strings to one string. Finally, we give a lower bound on the time-space product for LCE data structures in the non-uniform cell probe model showing that our second trade-off is nearly optimal.
The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem. Our first result is a randomized distributed algorithm that constructs a spanning tree of maximum degree $hat d = O(dlog{n})$. It requires $O((D + sqrt{n}) log^2 n)$ rounds (w.h.p.), where $D$ is the graph diameter, which matches (within log factors) the optimal round complexity for the related minimum spanning tree problem. Our second result refines this approximation factor by constructing a tree with maximum degree $hat d = O(d + log{n})$, though at the cost of additional polylogarithmic factors in the round complexity. Although efficient approximation algorithms for the MDST problem have been known in the sequential setting since the 1990s, our results are first efficient distributed solutions for this problem.
Given a set $P$ of $n$ red and blue points in the plane, a emph{planar bichromatic spanning tree} of $P$ is a spanning tree of $P$, such that each edge connects between a red and a blue point, and no two edges intersect. In the bottleneck planar bichromatic spanning tree problem, the goal is to find a planar bichromatic spanning tree $T$, such that the length of the longest edge in $T$ is minimized. In this paper, we show that this problem is NP-hard for points in general position. Moreover, we present a polynomial-time $(8sqrt{2})$-approximation algorithm, by showing that any bichromatic spanning tree of bottleneck $lambda$ can be converted to a planar bichromatic spanning tree of bottleneck at most $8sqrt{2}lambda$.
We show that there are CNF formulas which can be refuted in resolution in both small space and small width, but for which any small-width proof must have space exceeding by far the linear worst-case upper bound. This significantly strengthens the space-width trade-offs in [Ben-Sasson 09]}, and provides one more example of trade-offs in the supercritical regime above worst case recently identified by [Razborov 16]. We obtain our results by using Razborovs new hardness condensation technique and combining it with the space lower bounds in [Ben-Sasson and Nordstrom 08].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
