@inproceedings{mahabadi2025sublinear,
author = {Mahabadi, Sepideh and Roghani, Mohammad and Tarnawski, Jakub and Vakilian, Ali},
title = {Sublinear Metric Steiner Tree via Improved Bounds for Set Cover},
booktitle = {Innovations in Theoretical Computer Science (ITCS)},
year = {2025},
month = {January},
abstract = {We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of  points  in a metric space given to us by means of query access to an  matrix , and a set of terminals , the goal is to find the minimum-weight subset of the edges that connects all the terminal vertices. Recently, Chen, Khanna and Tan [SODA'23] gave an algorithm that uses Õ queries and outputs a -estimate of the metric Steiner tree weight, where  is a universal constant. A key component in their algorithm is a sublinear algorithm for a particular set cover problem where, given a set system , the goal is to provide a multiplicative-additive estimate for . Here  is the set of elements,  is the collection of sets, and  denotes the optimal set cover size of . In particular, their algorithm returns a -multiplicative-additive estimate for this set cover problem using  membership oracle queries (querying whether a set  contains an ), where  is a fixed constant. In this work, we improve the query complexity of -estimating the metric Steiner tree weight to  by showing a -estimate for the above set cover problem using Õ membership queries. To design our set cover algorithm, we estimate the size of a random greedy maximal matching for an auxiliary multigraph that the algorithm constructs implicitly, without access to its adjacency list or matrix.},
url = {http://approjects.co.za/?big=en-us/research/publication/sublinear-metric-steiner-tree-via-improved-bounds-for-set-cover/},
}