Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew routing techniques and their applications
194
0
0.0
(
0
)
Added by
Roei Tov
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $tilde O(frac{1}{epsilon} n^{2/3})$ space at each vertex and $tilde O(1/epsilon)$-bit headers, to route a message between any pair of vertices $u,vin V$ on a $(2 + epsilon,1)$-stretch path, i.e., a path of length at most $(2+epsilon)cdot d(u,v)+1$. This should be compared to the $(2,1)$-stretch and $tilde O(n^{5/3})$ space distance oracle of Patrascu and Roditty [FOCS10 and SIAM J. Comput. 2014] and to the $(2,1)$-stretch routing scheme of Abraham and Gavoille [DISC11] that uses $tilde O( n^{3/4})$ space at each vertex. - A routing scheme for weighted graphs with normalized diameter $D$, that uses $tilde O(frac{1}{epsilon} n^{1/3}log D)$ space at each vertex and $tilde O(frac{1}{epsilon}log D)$-bit headers, to route a message between any pair of vertices on a $(5+epsilon)$-stretch path. This should be compared to the $5$-stretch and $tilde O(n^{4/3})$ space distance oracle of Thorup and Zwick [STOC01 and J. ACM. 2005] and to the $7$-stretch routing scheme of Thorup and Zwick [SPAA01] that uses $tilde O( n^{1/3})$ space at each vertex. Since a $5$-stretch routing scheme must use tables of $Omega( n^{1/3})$ space our result is almost tight. - For an integer $ell>1$, a routing scheme for unweighted graphs that uses $tilde O(ellfrac{1}{epsilon} n^{ell/(2ell pm 1)})$ space at each vertex and $tilde O(frac{1}{epsilon})$-bit headers, to route a message between any pair of vertices on a $(3pm2/ell+epsilon,2)$-stretch path. - A routing scheme for weighted graphs, that uses $tilde O(frac{1}{epsilon}n^{1/k}log D)$ space at each vertex and $tilde O(frac{1}{epsilon}log D)$-bit headers, to route a message between any pair of vertices on a $(4k-7+epsilon)$-stretch path.
rate research
Read More
We introduce polyhedra circuits. Each polyhedra circuit characterizes a geometric region in $mathbb{R}^d$. They can be applied to represent a rich class of geometric objects, which include all polyhedra and the union of a finite number of polyhedra. They can be used to approximate a large class of $d$-dimensional manifolds in $mathbb{R}^d$. Barvinok developed polynomial time algorithms to compute the volume of a rational polyhedra, and to count the number of lattice points in a rational polyhedra in a fixed dimensional space $mathbb{R}^d$ with a fix $d$. Define $T_V(d,, n)$ be the polynomial time in $n$ to compute the volume of one rational polyhedra, $T_L(d,, n)$ be the polynomial time in $n$ to count the number of lattice points in one rational polyhedra with $d$ be a fixed dimensional number, $T_I(d,, n)$ be the polynomial time in $n$ to solve integer linear programming time with $d$ be the fixed dimensional number, where $n$ is the total number of linear inequalities from input polyhedra. We develop algorithms to count the number of lattice points in the geometric region determined by a polyhedra circuit in $Oleft(ndcdot r_d(n)cdot T_V(d,, n)right)$ time and to compute the volume of the geometric region determined by a polyhedra circuit in $Oleft(ncdot r_d(n)cdot T_I(d,, n)+r_d(n)T_L(d,, n)right)$ time, where $n$ is the number of input linear inequalities, $d$ is number of variables and $r_d(n)$ be the maximal number of regions that $n$ linear inequalities with $d$ variables partition $mathbb{R}^d$.
In this paper, we show a connection between a certain online low-congestion routing problem and an online prediction of graph labeling. More specifically, we prove that if there exists a routing scheme that guarantees a congestion of $alpha$ on any edge, there exists an online prediction algorithm with mistake bound $alpha$ times the cut size, which is the size of the cut induced by the label partitioning of graph vertices. With previous known bound of $O(log n)$ for $alpha$ for the routing problem on trees with $n$ vertices, we obtain an improved prediction algorithm for graphs with high effective resistance. In contrast to previous approaches that move the graph problem into problems in vector space using graph Laplacian and rely on the analysis of the perceptron algorithm, our proof are purely combinatorial. Further more, our approach directly generalizes to the case where labels are not binary.
MAXCUT defines a classical NP-hard problem for graph partitioning and it serves as a typical case of the symmetric non-monotone Unconstrained Submodular Maximization (USM) problem. Applications of MAXCUT are abundant in machine learning, computer vision and statistical physics. Greedy algorithms to approximately solve MAXCUT rely on greedy vertex labelling or on an edge contraction strategy. These algorithms have been studied by measuring their approximation ratios in the worst case setting but very little is known to characterize their robustness to noise contaminations of the input data in the average case. Adapting the framework of Approximation Set Coding, we present a method to exactly measure the cardinality of the algorithmic approximation sets of five greedy MAXCUT algorithms. Their information contents are explored for graph instances generated by two different noise models: the edge reversal model and Gaussian edge weights model. The results provide insights into the robustness of different greedy heuristics and techniques for MAXCUT, which can be used for algorithm design of general USM problems.
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $lambda$ then spectral independence holds at $lambda$. As a consequence, for Holant-type problems (e.g., spin systems) on bounded-degree graphs, we obtain optimal $O(nlog n)$ mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvinok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i.e., edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an $O(nlog{n})$ sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an $O(nlog{n})$ sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.
Perturbed graphic matroids are binary matroids that can be obtained from a graphic matroid by adding a noise of small rank. More precisely, r-rank perturbed graphic matroid M is a binary matroid that can be represented in the form I +P, where I is the incidence matrix of some graph and P is a binary matrix of rank at most r. Such matroids naturally appear in a number of theoretical and applied settings. The main motivation behind our work is an attempt to understand which parameterized algorithms for various problems on graphs could be lifted to perturbed graphic matroids. We study the parameterized complexity of a natural generalization (for matroids) of the following fundamental problems on graphs: Steiner Tree and Multiway Cut. In this generalization, called the Space Cover problem, we are given a binary matroid M with a ground set E, a set of terminals Tsubseteq E, and a non-negative integer k. The task is to decide whether T can be spanned by a subset of Esetminus T of size at most k. We prove that on graphic matroid perturbations, for every fixed r, Space Cover is fixed-parameter tractable parameterized by k. On the other hand, the problem becomes W[1]-hard when parameterized by r+k+|T| and it is NP-complete for rleq 2 and |T|leq 2. On cographic matroids, that are the duals of graphic matroids, Space Cover generalizes another fundamental and well-studied problem, namely Multiway Cut. We show that on the duals of perturbed graphic matroids the Space Cover problem is fixed-parameter tractable parameterized by r+k.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
