3 papers
cs.DS2025
Improved Additive Approximation Algorithms for APSP
Ce Jin, Yael Kirkpatrick, Michał Stawarz +1
The All-Pairs Shortest Paths (APSP) is a foundational problem in theoretical computer science. Approximating APSP in undirected unweighted graphs has been studied for many years, b…
cs.DS2025
All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin +2
We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most distinct weights on the outgoing edges from every node. For this…
cs.DS2025
Beyond 2-approximation for k-Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams +1
We consider the classical -Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even -approximations r…