3 citations · 3 across the 5 of their papers we have counts for
6 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…
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation
Alina Harbuzova, Ce Jin, Virginia Vassilevska Williams +1
Roundtrip spanners are the analog of spanners in directed graphs, where the roundtrip metric is used as a notion of distance. Recent works have shown existential results of roundtr…
Listing 6-Cycles
Ce Jin, Virginia Vassilevska Williams, Renfei Zhou
Listing copies of small subgraphs (such as triangles, -cycles, small cliques) in the input graph is an important and well-studied problem in algorithmic graph theory. In this pa…
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…