Back to Search
Start Over
HEURISTICS WITH CONSTANT ERROR GUARANTEES FOR THE DESIGN OF TREE NETWORKS.
- Source :
- Management Science; Mar88, Vol. 34 Issue 3, p331-341, 11p
- Publication Year :
- 1988
-
Abstract
- A tree network is a collection of trees rooted at a common central node. Several types of network design problems can be viewed as requiring the formation of a spanning tree network of minimum length, subject to a bound on the sum of "weights" on the nodes of any component tree. Such problems are NP-complete, and experience has shown that only small examples can be solved to optimality. This paper describes an efficient heuristic algorithm based on partitioning of a traveling salesman tour. When all the nodes have a unit weight and the bound is K, the heuristic finds a solution whose cost is at most 3 - 2/K times the minimum; in the general case the error bound is 4. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00251909
- Volume :
- 34
- Issue :
- 3
- Database :
- Complementary Index
- Journal :
- Management Science
- Publication Type :
- Academic Journal
- Accession number :
- 7358674
- Full Text :
- https://doi.org/10.1287/mnsc.34.3.331