On the approximability of Dense Steiner Problems
Abstract
We study the approximation complexity of the @e-Dense Steiner Tree Problem which was introduced by Karpinski and Zelikovsky (1998) [13]. They proved that for each @e>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 @e-Dense k-Steiner Tree Problem, the @e-Dense Prize Collecting Steiner Tree Problem and the @e-Dense Group Steiner Tree Problem. We also show that the @e-Dense Steiner Forest Problem is approximable within ratio 1+O((@?"ilog|S"i|)/(@?"i|S"i|)) where S"1,...,S"n 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.
References
[1]
Archer, A., Bateni, M., Hajiaghayi, M. and Karloff, H., Improved approximation algorithms for prize-collecting Steiner Tree and TSP. In: Proc. 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 427-436.
[2]
Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM. v45 i5. 753-782.
[3]
Arora, S. and Karakostas, G., A 2+epsilon approximation for the k-MST problem. In: Proc. SIAM Symp. Discrete Algorithms (SODA),
[4]
Byrka, J., Grandoni, F., Rothfoss, Th. and Sanita, L., An improved LP-based approximation for Steiner Tree. In: Proc. STOC, pp. 583-592.
[5]
Cardinal, J., Karpinski, M., Schmied, R. and Viehmann, C., Approximating subdense instances of covering problems. Electronic Notes in Discrete Mathematics. v37. 297-302.
[6]
Chlebikov, M. and Chlebikova, J., Approximation hardness of the Steiner Tree Problem on graphs. In: LNCS, vol. 2368. pp. 170-179.
[7]
Dreyfus, S.E. and Wagner, R.A., The Steiner Problem in graphs. Networks. v1. 195-207.
[8]
Garg, N., Konjevod, G. and Ravi, A polylogarithmic approximation algorithm for the Group Steiner Tree Problem. In: SODA: ACM-SIAM Symposium on Discrete Algorithms,
[9]
Goemans, M. and Williamson, D., A general approximation technique for constrained forest problems. In: SODA: ACM-SIAM Symposium on Discrete Algorithms,
[10]
Steiner's Problem in graphs and its implications. Networks. v1. 113-133.
[11]
Halperin, E. and Krauthgamer, R., Polylogarithmic inapproximability. In: Proc. of STOC,
[12]
Hauptmann, M., On the approximability of Dense Steiner Tree Problems. In: Proc. Tenth Italian Conference on Theoretical Computer Science, World Scientific. pp. 15-26.
[13]
Karpinski, M. and Zelikovsky, A., Approximating dense cases of covering problems. In: DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 40. pp. 169-178.
[14]
Ravi, R., A primal-dual approximation algorithm for the Steiner Forest Problem. Information Processing Letters. v50 i4. 185-190.
[15]
Robins, G. and Zelikovsky, A., Improved Steiner Tree approximation in graphs. In: Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM. pp. 770-779.
- On the approximability of Dense Steiner Problems
Recommendations
Approximating the selected-internal Steiner tree
In this paper, we consider a variant of the well-known Steiner tree problem. Given a complete graph G=(V,E) with a cost function c:E->R^+ and two subsets R and R^' satisfying R^'@?R@?V, a selected-internal Steiner tree is a Steiner tree which contains (...
Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems
Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an $O(\log n)$-approximation algorithm for the node-weighted prize-collecting ...
On the hardness of full Steiner tree problems
Given a weighted graph G = ( V , E ) and a subset R of V, a Steiner tree in G is a tree which spans all vertices in R. The vertices in V R are called Steiner vertices. A full Steiner tree is a Steiner tree in which each vertex of R is a leaf. The full ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V. © 2013.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 July 2013
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 01 Jan 2025