Image de couverture de livre

Improved Additive Approximation Algorithms for APSP

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Jin, Ce, Kirkpatrick, Yael, Stawarz, Michał, Williams, Virginia Vassilevska
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Beyond 2-approximation for k-Center in Graphs
par: Jin, Ce, et autres
Publié: (2025)

Shortest Paths in Multimode Graphs
par: Kirkpatrick, Yael, et autres
Publié: (2025)

New Diameter Approximations via Distance Oracle Techniques
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
par: Nogler, Jakob, et autres
Publié: (2024)

Faster Algorithms for Text-to-Pattern Hamming Distances
par: Chan, Timothy M., et autres
Publié: (2023)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
par: Roditty, Liam, et autres
Publié: (2025)

Fast Approximate Counting of Cycles
par: Censor-Hillel, Keren, et autres
Publié: (2024)

All-Pairs Shortest Paths with Few Weights per Node
par: Abboud, Amir, et autres
Publié: (2025)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
par: Nogler, Jakob, et autres
Publié: (2026)

Listing 6-Cycles in Sparse Graphs
par: Williams, Virginia Vassilevska, et autres
Publié: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
par: Bodwin, Greg, et autres
Publié: (2024)

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms
par: Kirkpatrick, Yael, et autres
Publié: (2024)

Improved girth approximation in weighted undirected graphs
par: Kadria, Avi, et autres
Publié: (2025)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
par: Censor-Hillel, Keren, et autres
Publié: (2025)

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
par: Koo, Jaehyun
Publié: (2024)

A Refined Laser Method and Faster Matrix Multiplication
par: Alman, Josh, et autres
Publié: (2020)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
par: Dalirrooyfard, Mina, et autres
Publié: (2023)

All-Hops Shortest Paths
par: Williams, Virginia Vassilevska, et autres
Publié: (2024)

Bootstrapping Dynamic APSP via Sparsification
par: Kyng, Rasmus, et autres
Publié: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
par: Akmal, Shyan, et autres
Publié: (2024)

A Simple Dynamic Spanner via APSP
par: Kyng, Rasmus, et autres
Publié: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
par: Fischer, Nick
Publié: (2026)

Approximately Counting Knapsack Solutions in Subquadratic Time
par: Feng, Weiming, et autres
Publié: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
par: Jin, Ce, et autres
Publié: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
par: Jin, Ce, et autres
Publié: (2024)

Faster Cycle Detection in the Congested Clique
par: Censor-Hillel, Keren, et autres
Publié: (2024)

Streaming Algorithms for Connectivity Augmentation
par: Jin, Ce, et autres
Publié: (2024)

0-1 Knapsack in Nearly Quadratic Time
par: Jin, Ce
Publié: (2023)

Memory Reallocation with Polylogarithmic Overhead
par: Jin, Ce
Publié: (2026)

Improved Approximation Algorithms for Three-Dimensional Knapsack
par: Jansen, Klaus, et autres
Publié: (2025)

Improved Approximation Algorithm for Maximum Balanced Biclique
par: Manurangsi, Pasin
Publié: (2026)

An Improved Approximation Algorithm for Metric Triangle Packing
par: Zhao, Jingyang, et autres
Publié: (2024)

More Asymmetry Yields Faster Matrix Multiplication
par: Alman, Josh, et autres
Publié: (2024)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
par: Zhao, Jingyang, et autres
Publié: (2025)

Improved Approximation Algorithms for Non-Preemptive Throughput Maximization
par: Armbruster, Alexander, et autres
Publié: (2026)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
par: Zhao, Jingyang, et autres
Publié: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
par: Fan, Chenglin, et autres
Publié: (2025)

Improved Approximation Algorithms for Capacitated Vehicle Routing with Fixed Capacity
par: Zhao, Jingyang, et autres
Publié: (2022)

Improved Approximation Algorithms for Relational Clustering
par: Esmailpour, Aryan, et autres
Publié: (2024)