Bottleneck Steiner tree with bounded number of Steiner vertices. (English) Zbl 1320.68225
Summary: Given a complete graph \(G = (V, E)\), where each vertex is labeled either terminal or Steiner, a distance function (i.e., a metric) \(d : E \to \mathbb{R}^+\), and a positive integer \(k\), we study the problem of finding a Steiner tree \(T\) spanning all terminals and at most \(k\) Steiner vertices, such that the length of the longest edge is minimized. We first show that this problem is NP-hard and cannot be approximated within a factor of \(2 - \varepsilon\), for any \(\varepsilon > 0\), unless \(\mathrm P=\mathrm{NP}\). Then, we present a polynomial-time 2-approximation algorithm for this problem.
MSC:
| 68W25 | Approximation algorithms |
| 05C12 | Distance in graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Abu-Affash, A. K., On the Euclidean bottleneck full Steiner tree problem, (Proceedings of the 27th ACM Symposium on Computational Geometry. Proceedings of the 27th ACM Symposium on Computational Geometry, SoCG ’11 (2011)), 433-439 · Zbl 1283.68335 |
| [2] | Abu-Affash, A. K.; Carmi, P.; Katz, M. J.; Segal, M., The Euclidean bottleneck Steiner path problem, (Proceedings of the 27th ACM Symposium on Computational Geometry. Proceedings of the 27th ACM Symposium on Computational Geometry, SoCG ’11 (2011)), 440-447 · Zbl 1283.68336 |
| [3] | Arora, S., Polynomial time approximation schemes for Euclidean TSP and other geometric problems, J. ACM, 45, 735-782 (1998) · Zbl 1064.90566 |
| [4] | Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and hardness of approximation problems, (Proceedings of the 33rd Annual Symposium on Foundations of Computer Science. Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, FOCS ’92 (1992)), 14-23 · Zbl 0977.68539 |
| [5] | Bae, S. W.; Lee, C.; Choi, S., On exact solutions to the Euclidean bottleneck Steiner tree problem, Inf. Process. Lett., 110, 672-678 (2010) · Zbl 1234.68126 |
| [6] | Berman, P.; Ramaiyer, V., Improved approximation for the Steiner tree problem, J. Algorithms, 17, 381-408 (1994) · Zbl 0820.68049 |
| [7] | Borchers, A.; Du, D.-Z., The \(k\)-Steiner ratio in graphs, SIAM J. Comput., 26, 857-869 (1997) · Zbl 0870.68109 |
| [8] | Byrka, J.; Grandoni, F.; Rothvoß, T.; Sanità, Laura, An improved LP-based approximation for Steiner tree, (Proceedings of the 42nd ACM Symposium on Theory of Computing. Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC ’10 (2010)), 583-592 · Zbl 1293.05039 |
| [9] | (Cheng, X.; Du, D.-Z., Steiner Trees in Industry (2001), Kluwer Academic Publishers) |
| [10] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), The MIT Press · Zbl 1187.68679 |
| [11] | (Du, D.-Z.; Smith, J. M.; Rubinstein, J. H., Advances in Steiner Trees (2000), Kluwer Academic Publishers) · Zbl 0932.00010 |
| [12] | Duin, C. W.; Volgenant, A., The partial sum criterion for Steiner trees in graphs and shortest paths, Eur. J. Oper. Res., 97, 172-182 (1997) · Zbl 0922.90139 |
| [13] | Garey, M. R.; Johnson, D. S., The rectilinear Steiner tree problem is NP-complete, SIAM J. Appl. Math., 32, 4, 826-834 (1977) · Zbl 0396.05009 |
| [14] | Garey, M. R.; Graham, R. L.; Johnson, D. S., The complexity of computing Steiner minimal trees, SIAM J. Appl. Math., 32, 4, 835-859 (1977) · Zbl 0399.05023 |
| [15] | Hougardy, S.; Prömel, H. J., A 1.598 approximation algorithm for the Steiner problem in graphs, (Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00 (1999)), 448-453 · Zbl 0946.68107 |
| [16] | Hwang, F. K.; Richards, D. S.; Winter, P., The Steiner Tree Problem, Annals of Discrete Mathematics, Amsterdam (1992) · Zbl 0774.05001 |
| [17] | Kahng, A. B.; Robins, G., On Optimal Interconnection for VLSI (1995), Kluwer Academic Publishers · Zbl 0826.68067 |
| [18] | Karpinski, M.; Zelikovsky, A., New approximation algorithms for the Steiner tree problem, J. Comb. Optim., 1, 1, 47-65 (1997) · Zbl 0895.90171 |
| [19] | Li, Z.-M.; Zhu, D.-M.; Ma, S.-H., Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane, J. Comput. Sci. Technol., 19, 6, 791-794 (2004) |
| [20] | Prömel, H. J.; Steger, A., A new approximation algorithm for the Steiner tree problem with performance ratio 5/3, J. Algorithms, 36, 1, 89-101 (2000) · Zbl 0959.68101 |
| [21] | Robbins, G.; Zelikovsky, A., Tighter bounds for graph Steiner tree approximation, SIAM J. Discrete Math., 19, 1, 122-134 (2005) · Zbl 1082.05088 |
| [22] | Sarrafzadeh, M.; Wong, C. K., Bottleneck Steiner trees in the plane, IEEE Trans. Comput., 41, 3, 370-374 (1992) · Zbl 1395.68219 |
| [23] | Wang, L.; Du, D.-Z., Approximations for a bottleneck Steiner tree problem, Algorithmica, 32, 554-561 (2002) · Zbl 1004.68126 |
| [24] | Wang, L.; Li, Z.-M., Approximation algorithm for a bottleneck \(k\)-Steiner tree problem in the Euclidean plane, Inf. Process. Lett., 81, 151-156 (2002) · Zbl 1032.68163 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
