New tight bounds improve estimating metric steiner tree costs

Tight Bounds for Sublinear Metric Steiner Tree

Data Structures and Algorithms

Summary

The problem involves finding the cheapest way to connect a special group of points with a tree, possibly using other points to save cost. The authors focus on estimating this cost quickly without checking every distance between points. Previous methods could get an estimate within twice the actual cost but required many distance checks. The authors present a method that estimates the cost slightly better than twice the actual cost using significantly fewer distance checks and prove this efficiency can’t be improved much further.

What this means in practice

  • For network planners: Estimate minimum infrastructure cost connecting key locations faster using fewer distance measurements.
  • For urban transit designers: Quickly approximate minimal route designs linking transit terminals without exhaustive distance checks.

A theory result. No direct application yet.

Authors

Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian

Abstract

In the metric Steiner tree problem we are given an $n$-point metric space $(V,w)$ and a set $T\subseteq V$ of terminals, and we seek the smallest weight $\mathrm{OPT}$ of a tree that spans $T$ and may use points of $V\setminus T$. We study sublinear algorithms in the distance-oracle model, where the algorithm knows $V$ and $T$ upfront and can query the distance function $w$. The objective is to estimate $\mathrm{OPT}$ while querying significantly fewer than $n^2$ distances. The minimum spanning tree on $T$ estimates $\mathrm{OPT}$ within a factor $2$, and its weight can be approximated with $\widetilde{O}(n)$ queries. The natural question that has been studied is therefore the query complexity of estimating $\mathrm{OPT}$ within a factor strictly below $2$. Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using $\widetilde{O}(n^{13/7})$ queries, and a lower bound of $\widetildeΩ(n^{6/5})$. Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to $\widetilde{O}(n^{5/3})$, and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to $\widetildeΩ(n^{7/5})$. In this work we settle the above question. We give an algorithm that estimates $\mathrm{OPT}$ within a factor $2-η_0$, for an absolute constant $η_0>0$, with query (and time) complexity $\widetilde{O}(n^{3/2})$. We also show that the exponent $3/2$ is tight.