# Fast Computation on Semirings Isomorphic to $(\times, \max)$ on $\mathbb{R}_+$

Preprint · Oliver Serang

- Archive id: arxiv:1511.05690
- Published: 2015-11-18
- arXiv: https://arxiv.org/abs/1511.05690
- Source URL: https://arxiv.org/abs/1511.05690
- PDF: https://arxiv.org/pdf/1511.05690
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.