4 papers
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…
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…
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…
Faster Algorithms for Text-to-Pattern Hamming Distances
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams +1
We study the classic Text-to-Pattern Hamming Distances problem: given a pattern of length and a text of length , both over a polynomial-size alphabet, compute the Ha…