Heuristics with Constant Error Guarantees for the Design of Tree Networks
提出一种基于旅行商环游分割的高效启发式算法，用于求解受节点权重和约束的最小生成树网络问题，并给出常数误差界（单位权重时误差不超过3-2/K，一般情况不超过4）。
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.