ﻻ يوجد ملخص باللغة العربية
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.
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.
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 e
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 vis
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 spec
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 th