Heuristics with Constant Error Guarantees for the Design of Tree Networks

Kemal Altinkemer and Bezalel Gavish
Additional contact information
Kemal Altinkemer: Krannert Graduate School of Management, Purdue University, West Lafayette, Indiana 47907
Bezalel Gavish: Department of Administrative Sciences, Naval Postgraduate School, Monterey, California 93943

Management Science, 1988, vol. 34, issue 3, 331-341

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.

Keywords: networks/graphs:; design; heuristics (search for similar items in EconPapers)
Date: 1988
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.34.3.331 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:34:y:1988:i:3:p:331-341

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().