Manoj Gupta Extends 2-Approximation to Close Network Pairs, Breaking a 1996 Limit
Updated
Updated · ScienceDaily · Oct 30
Manoj Gupta Extends 2-Approximation to Close Network Pairs, Breaking a 1996 Limit
1 articles · Updated · ScienceDaily · Oct 30
Summary
Gupta’s new algorithm guarantees 2-approximate shortest-path estimates for much closer vertex pairs, advancing a limitation that had persisted since the 1996 DHZ result.
The method keeps the earlier approach’s near-optimal runtime by replacing single-layer sampling with multi-scale sampling, which captures short routes previous estimates could miss.
The original DHZ algorithm already worked well for far-apart points in large graphs, but its accuracy guarantee could fail on nearby pairs when sampled vertices lay too far from the true shortest path.
Presented at FOCS 2025, the result strengthens theory behind all-pairs shortest paths in massive networks used in transport, communications, biology and AI, where fast, reliable estimates matter more than exact distances.