  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,v\in 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 [FOCS'10
and SIAM J. Comput. 2014] and to the $(2,1)$-stretch routing scheme of Abraham
and Gavoille [DISC'11] 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 [STOC'01 and J. ACM. 2005] and to the $7$-stretch routing scheme of
Thorup and Zwick [SPAA'01] 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(\ell\frac{1}{\epsilon} n^{\ell/(2\ell \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 $(3\pm2/\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.
