Tight Bounds for Sublinear Metric Steiner Tree
In the authors' words
In the metric Steiner tree problem we are given an -point metric space and a set of terminals, and we seek the smallest weight of a tree that spans and may use points of . We study sublinear algorithms in the distance-oracle model, where the algorithm knows and upfront and can query the distance function . The objective is to estimate while querying significantly fewer than distances. The minimum spanning tree on estimates within a factor , and its weight can be approximated with queries. The natural question that has been studied is therefore the query complexity of estimating within a factor strictly below . Chen, Khanna, and Tan [SODA 2023] gave such an algorithm using queries, and a lower bound of . Later Mahabadi, Roghani, Tarnawski, and Vakilian [ITCS 2025] improved the algorithm to , and Mahabadi, Tarnawski, and Vakilian [ITCS 2027] improved the lower bound to . In this work we settle the above question. We give an algorithm that estimates within a factor , for an absolute constant , with query (and time) complexity . We also show that the exponent is tight.
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.