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

CREATORLiam Roditty, Ariel Sapir
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE1.9 MB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-04640

Browse the full library · About the Tower of Babel