Skip to main content

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.

By Mei Ling Tan

Diagram of connected points with several possible routes highlighted
Photo: ScienceDaily

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.

Keep reading: Tech News

All Tech News stories

Latest in Technology

All latest
  1. Tech News

    OpenAI tests ChatGPT dot with Plus subscribers, widens Business access

  2. Tech News

    Google adds Gemini chats to Search homepage in global desktop rollout

  3. Tech News

    Apple job postings outline plans for autonomous AI assistants

  4. Tech News

    Google tests quantum contextuality with as many as 105 qubits

  5. Tech News

    Microsoft brings Office apps into Copilot and adds AI management tools

  6. Tech News

    Everful raises US$48.5 million to expand AI sourcing business