Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlgorithms for Euclidean Degree Bounded Spanning Tree Problems
76
0
0.0
(
0
)
Added by
Patrick Andersen
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Given a set of points in the Euclidean plane, the Euclidean textit{$delta$-minimum spanning tree} ($delta$-MST) problem is the problem of finding a spanning tree with maximum degree no more than $delta$ for the set of points such the sum of the total length of its edges is minimum. Similarly, the Euclidean textit{$delta$-minimum bottleneck spanning tree} ($delta$-MBST) problem, is the problem of finding a degree-bounded spanning tree for a set of points in the plane such that the length of the longest edge is minimum. When $delta leq 4$, these two problems may yield disjoint sets of optimal solutions for the same set of points. In this paper, we perform computational experiments to compare the accuracies of a variety of heuristic and approximation algorithms for both these problems. We develop heuristics for these problems and compare them with existing algorithms. We also describe a new type of edge swap algorithm for these problems that outperforms all the algorithms we tested.
rate research
Read More
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.
The geometric $delta$-minimum spanning tree problem ($delta$-MST) is the problem of finding a minimum spanning tree for a set of points in a normed vector space, such that no vertex in the tree has a degree which exceeds $delta$, and the sum of the lengths of the edges in the tree is minimum. The similarly defined geometric $delta$-minimum bottleneck spanning tree problem ($delta$-MBST), is the problem of finding a degree bounded spanning tree such that the length of the longest edge is minimum. For point sets that lie in the Euclidean plane, both of these problems have been shown to be NP-hard for certain specific values of $delta$. In this paper, we investigate the $delta$-MBST problem in $3$-dimensional Euclidean space and $3$-dimensional rectilinear space. We show that the problems are NP-hard for certain values of $delta$, and we provide inapproximability results for these cases. We also describe new approximation algorithms for solving these $3$-dimensional variants, and then analyse their worst-case performance.
We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an $n$-qubit product state $|vrangle$ with mean energy $e_0=langle v|H|vrangle$ and variance $mathrm{Var}=langle v|(H-e_0)^2|vrangle$, and outputs a state with an energy that is lower than $e_0$ by an amount proportional to $mathrm{Var}^2/n$. In a typical case, we have $mathrm{Var}=Omega(n)$ and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to $k$-local Hamiltonians and entangled initial states.
In the Priority Steiner Tree (PST) problem, we are given an undirected graph $G=(V,E)$ with a source $s in V$ and terminals $T subseteq V setminus {s}$, where each terminal $v in T$ requires a nonnegative priority $P(v)$. The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from $s$ to each terminal $v$ consists of edges of rate greater than or equal to $P(v)$. The PST problem with $k$ priorities admits a $min{2 ln |T| + 2, krho}$-approximation [Charikar et al., 2004], and is hard to approximate with ratio $c log log n$ for some constant $c$ [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the $(2 ln |T| + 2)$-approximation to show an approximation ratio of $lceil log_2 |T| rceil + 1 le 1.443 ln |T| + 2$, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a $(2 ln |T|+2)$-approximation using extensions of the spider decomposition by [Klein & Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight.
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all $k$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of the $(ktimes k)$-wall or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $tgeq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a $t$-theta for some $tgeq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every $Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
