On greedy heuristic for Steiner minimum trees. (English) Zbl 0827.68086
Summary: We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to \(\sqrt {3}/2\). We also propose a new conjecture.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | P. Berman and V. Ramaiye, An approximation algorithm for the Steiner tree problem,Journal of Algorithms,17 (1994), 381-408. · Zbl 0820.68049 · doi:10.1006/jagm.1994.1041 |
| [2] | F. R. K. Chung and R. L. Graham, A new bound for Euclidean Steiner minimum trees,Annals of the New York Academy of Sciences,440 (1985), 328-346. · Zbl 0572.05022 · doi:10.1111/j.1749-6632.1985.tb14564.x |
| [3] | F. R. K. Chung and F. K. Hwang, A lower bound for the Steiner tree problem,SIAM Journal of Applied Mathematics,34 (1978), 27-36. · Zbl 0376.05020 · doi:10.1137/0134003 |
| [4] | T. Cole, A problem in Steiner networks, Manuscript. |
| [5] | D. Z. Du and F. K. Hwang, A new bound for the Steiner ratio,Transactions of the American Mathematical Society,278 (1983), 137-148. · Zbl 0523.51017 · doi:10.1090/S0002-9947-1983-0697065-3 |
| [6] | D. Z. Du and F. K. Hwang, A proof of the Gilbert-Pollak conjecture on the Steiner ratio,Algorithmica,7 (1992), 121-135. · Zbl 0774.05027 · doi:10.1007/BF01758755 |
| [7] | D. Z. Du, Y. Zhang, and Q. Feng, On better heuristic for Euclidean Steiner minimum trees,Proceedings of the and Symposium on the Foundations of Computer Science, 1991. |
| [8] | M. R. Garey, R. L. Graham, and D. S. Johnson, The complexity of computing Steiner minimal trees,SIAM Journal of Applied Mathematics,32 (1977), 835-859. · Zbl 0399.05023 · doi:10.1137/0132072 |
| [9] | E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM Journal of Applied Mathematics,16 (1968), 1-29. · Zbl 0159.22001 · doi:10.1137/0116001 |
| [10] | R. L. Graham and F. K. Hwang, Remarks on Steiner minimal trees,Bulletin of the Institute of Mathematics, Academia Sinica,4 (1976), 177-182. · Zbl 0333.05101 |
| [11] | H. O. Pollak, Some remarks on the Steiner problem,Journal of Combinatorial Theory, Series A,24 (1978), 278-295. · Zbl 0392.05021 · doi:10.1016/0097-3165(78)90058-4 |
| [12] | J. H. Rubinstein and D. A. Thomas, The Steiner ratio conjecture for six points,Journal of Combinatorial Theory, Series A,58 (1991), 54-77. · Zbl 0739.05034 · doi:10.1016/0097-3165(91)90073-P |
| [13] | J. H. Rubinstein and D. A. Thomas, The calculus of variations and the Steiner problem,Annals of Operations Research,33 (1991), 481-499. · Zbl 0734.05040 · doi:10.1007/BF02071984 |
| [14] | W. D. Smith and P. W. Shor, Steiner tree problems,Algorithmica,7 (1992), 329-332. · Zbl 0773.05042 · doi:10.1007/BF01758766 |
| [15] | Hong Yi, Yang Hongcang, and Du Dingzhu, An inequality for convex functions,Kexue Tongbao 27 (1982), 901-904. · Zbl 0516.26008 |
| [16] | A. Z. Zelikovsky, The 11/6-approximation algorithm for the Steiner problem on networks,Algorithmica,9 (1993), 463-470. · Zbl 0768.68192 · doi:10.1007/BF01187035 |
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.
