We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
HEURISTICS WITH CONSTANT ERROR GUARANTEES FOR THE DESIGN OF TREE NETWORKS.
- Authors
Altinkemer, Kemal; Gavish, Bezalel
- 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.
- Subjects
HEURISTIC; OPERATIONS research; MANAGEMENT science; NP-complete problems; COMPUTATIONAL complexity; ALGORITHMS; MATHEMATICAL programming; MATHEMATICAL optimization; NETWORK analysis (Planning)
- Publication
Management Science, 1988, Vol 34, Issue 3, p331
- ISSN
0025-1909
- Publication type
Article
- DOI
10.1287/mnsc.34.3.331