☆ 4.5 Article

Directed Shortest Paths via Approximate Cost Balancing

JOURNAL OF THE ACM (2023)

Near-linear convergence of the Random Osborne algorithm for Matrix Balancing

Jason M. Altschuler et al.

Summary: In this paper, a simple random variant of Osborne's algorithm is introduced, which achieves convergence in near-linear time for input sparsity. The authors also show that if the graph with adjacency matrix is moderately connected, the algorithm converges exponentially fast. Numerical precision issues are addressed and improved runtime bounds are established for various variants of Osborne's algorithm.

MATHEMATICAL PROGRAMMING (2023)

添加到收藏夹

Article Computer Science, Theory & Methods

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

Timothy M. Chan et al.

Summary: The study presents deterministic solutions for solving all-pairs shortest paths and counting orthogonal vector pairs in multiple dimensions. These results can lead to faster deterministic algorithms for various other problems and resolve an outstanding issue.

ACM TRANSACTIONS ON ALGORITHMS (2021)

添加到收藏夹

Article Computer Science, Hardware & Architecture