  We provide new tradeoffs between approximation and running time for the
decremental all-pairs shortest paths (APSP) problem. For undirected graphs with
$m$ edges and $n$ nodes undergoing edge deletions, we provide four new
approximate decremental APSP algorithms, two for weighted and two for
unweighted graphs. Our first result is $(2+ \epsilon)$-APSP with total update
time $\tilde{O}(m^{1/2}n^{3/2})$ (when $m= n^{1+c}$ for any constant $0<c<1$).
Prior to our work the fastest algorithm for weighted graphs with approximation
at most $3$ had total $\tilde O(mn)$ update time for $(1+\epsilon)$-APSP
[Bernstein, SICOMP 2016]. Our second result is $(2+\epsilon, W_{u,v})$-APSP
with total update time $\tilde{O}(nm^{3/4})$, where the second term is an
additive stretch with respect to $W_{u,v}$, the maximum weight on the shortest
path from $u$ to $v$.
  Our third result is $(2+ \epsilon)$-APSP for unweighted graphs in $\tilde
O(m^{7/4})$ update time, which for sparse graphs ($m=o(n^{8/7})$) is the first
subquadratic $(2+\epsilon)$-approximation. Our last result for unweighted
graphs is $(1+\epsilon, 2(k-1))$-APSP, for $k \geq 2 $, with
$\tilde{O}(n^{2-1/k}m^{1/k})$ total update time (when $m=n^{1+c}$ for any
constant $c >0$). For comparison, in the special case of $(1+\epsilon,
2)$-approximation, this improves over the state-of-the-art algorithm by
[Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of
$\tilde{O}(n^{2.5})$. All of our results are randomized, work against an
oblivious adversary, and have constant query time.
