On the approximability of Dense Steiner Problems

We study the approximation complexity of the ϵ-Dense Steiner Tree Problem which was introduced by Karpinski and Zelikovsky (1998) [13]. They proved that for each ϵ>0ϵ>0, this problem admits a PTAS. Based on their method we consider here dense versions of various Steiner Tree problems. In particular, we give polynomial time approximation schemes for the ϵ-Dense k-Steiner Tree Problem, the ϵ-Dense Prize Collecting Steiner Tree Problem and the ϵ-Dense Group Steiner Tree Problem. We also show that the ϵ  -Dense Steiner Forest Problem is approximable within ratio 1+O((∑ilog|Si|)/(∑i|Si|))1+O((∑ilog|Si|)/(∑i|Si|)) where S1,…,SnS1,…,Sn are the terminal sets of the given instance. This ratio becomes small when the number of terminal sets is small compared to the total number of terminals.