Tight Bounds for Sublinear Metric Steiner TreeResearch Paper
The metric Steiner tree problem asks for a cheapest tree connecting a prescribed set of terminals in a metric space, possibly through additional points. It is one of Karp's original NP-complete problems, with a best known polynomial-time ratio of (Byrka, Grandoni, Rothvoß, Sanità, J. ACM 2013).