  Important problems across multiple disciplines involve computations on the
semiring $(\times, \max)$ (or its equivalents, the negated version $(\times,
\min)$), the log-transformed version $(+, \max)$, or the negated
log-transformed version $(+, \min)$): max-convolution, all-pairs shortest paths
in a weighted graph, and finding the largest $k$ values in $x_i+y_j$ for two
lists $x$ and $y$. However, fast algorithms such as those enabling FFT
convolution, sub-cubic matrix multiplication, \emph{etc.}, require inverse
operations, and thus cannot be computed on semirings. This manuscript
generalizes recent advances on max-convolution: in this approach a small family
of $p$-norm rings are used to efficiently approximate results on a nonnegative
semiring. The general approach can be used to easily compute sub-cubic
estimates of the all-pairs shortest paths in a graph with nonnegative edge
weights and sub-quadratic estimates of the top $k$ values in $x_i+y_j$ when $x$
and $y$ are nonnegative. These methods are fast in practice and can benefit
from coarse-grained parallelization.
