{"id":"arxiv:1511.05690","kind":"preprint","title":"Fast Computation on Semirings Isomorphic to $(\\times, \\max)$ on $\\mathbb{R}_+$","authors":["Oliver Serang"],"author_count":1,"year":2015,"published":"2015-11-18","venue":null,"cited_by":null,"doi":null,"arxiv_id":"1511.05690","nct_id":null,"source_url":"https://arxiv.org/abs/1511.05690","archive_url":"https://space-kitty.com/papers/arxiv:1511.05690","updated":"2016-06-17","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1511.05690","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}