On greedy heuristics for steiner minimum trees |
| |
| Authors: | Ding -Zhu Du |
| |
| Affiliation: | (1) Department of Computer Science, University of Minnesota, 55455 Minneapolis, MN, USA;(2) Institute of Applied Mathematics, Chinese Academy of Sciences, 100080 Beijing, People's Republic of China |
| |
| Abstract: | 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 3/2. We also propose a new conjecture.Supported in part by the National Science Foundation under Grant CCR-9208913. |
| |
| Keywords: | Steiner trees Greed heuristic |
| 本文献已被 SpringerLink 等数据库收录！ |
|
