Computer scientist refines shortest-path algorithm, extending 1996 guarantee
Multi-scale sampling extends the 2-approximation guarantee to closer points without increasing overall runtime
A computer scientist has improved an algorithm for calculating shortest paths in large networks, extending a mathematical guarantee that had remained unchanged since 1996. Dr. Manoj Gupta of the Indian Institute of Technology Gandhinagar introduced a multi-scale sampling strategy that enables more reliable distance estimates for points close together, without slowing down the algorithm.