Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
Liam Roditty, Ariel Sapir · 2025
Read Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms by Liam Roditty, Ariel Sapir (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-04640.txt.
Introduction
Finding near-shortest paths between all pairs of nodes in a weighted graph is the problem addressed by Liam Roditty and one co-author in a 2025 algorithms paper. Exact answers can be costly, so they study approximations that allow small additive or multiplicative error. Their results cover dense weighted undirected graphs.
For additive approximation, they give an algorithm matching a classic dense-graph runtime while handling weights. For nearly additive approximation, they improve an earlier error bound. For multiplicative approximation, they present a framework that speeds up a previous dense-graph method and generalises a recent near-two approximation, clarifying trade-offs between error and runtime.
Catalog record
| CREATOR | Liam Roditty, Ariel Sapir |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 1.9 MB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-04640