pipette
ENEnglish

Tight Bounds for Sublinear Metric Steiner Tree

Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.