Algorithm widens accuracy guarantee for network distance calculations
The theoretical advance covers shorter connections while keeping the computational runtime of a method dating to 1996.
A refinement by computer scientist Manoj Gupta extends a mathematical guarantee for estimating distances in networks to points closer together, without requiring more overall computation time than an earlier approach. The result remains theoretical and does not demonstrate immediate gains for particular commercial systems.
Gupta, an associate professor at the Indian Institute of Technology Gandhinagar, presented the research at the 66th Annual Symposium on Foundations of Computer Science (FOCS 2025). His work concerns the All-Pairs Shortest Paths problem, which seeks minimum distances between all pairs of network points.
A 1996 algorithm from Dor, Halperin, and Zwick used selected points to make those estimates efficiently. It guaranteed estimates no higher than twice the true minimum distance when points were sufficiently separated, but could not consistently meet that standard for nearby pairs.
The new approach replaces a single sampling layer with sampling at several scales. That allows shorter routes to be captured and lowers the separation needed for the accuracy guarantee to apply, while retaining the earlier method’s overall computational complexity.
Distance calculations of this kind are relevant to transportation, communications and biological networks, where exact answers can require substantial computing time and memory.
