Algorithms for a Variant of the Full Steiner Tree Problem
Haiyan Wang, Binchao Huang, Jianping Li · 2021
This paper studies a variant of the Steiner tree problem in the Euclidean plane ℝ2: the minimum-number of a specific material for the full Steiner tree problem (MNFST, for short). This question is an extension of the Steiner tree problem and the full Steiner tree problem. It has a wide range of applications in real life. The MNFST has been shown to be NP-hard. In this paper, we propose two asymptotic polynomial-time approximation algorithms for this problem. These two algorithms satisfy OUT ≤ 2.428OPT + 1 and $OUT \leq 2.123sOPT + \frac{3}{2}$, respectively.