The Multi-Tier Tree Problem
The Multi-Tier Tree Problem
复制标题
多层树问题
DOI：
10.1287/ijoc.8.3.202
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Prakash Mirchandani
中科院分区：
文献类型：
--
作者：
Prakash Mirchandani
本文研究了多层树问题，它是Steiner树问题的推广，在该问题中，我们给出了一个图，图的节点被划分为几个层（等级），并且等级依赖于边成本。MTT问题寻求边的等级选择的成本最小化，使得每对节点，比如在层t′和t″ ≥ t′，通过包含等级t ′或更好（等级）边的路径连接。MTT问题出现在电信环境中（我们必须在竞争的通信技术之间进行选择），最终出现在交通环境中（所产生的成本决定了两点之间提供的接入类型）。在本文中，我们开发了两种解决方案的方法。首先，我们开发了一个递归启发式的MTT问题，并获得了数据独立的边界MTT问题的3层。对于一种情况，递归启发式算法的性能比的界限是1.52241。接下来，我们开发了一个基于双重的解决方案的过程中，这个问题，并将…
This paper studies the multi-tier tree (MTT) problem, a generalization of the Steiner-tree problem, in which we are given a graph with its nodes partitioned into several tiers (grades), and grade dependent edge-costs. The MTT problem seeks the cost minimizing choice of grades for the edges such that every pair of nodes, say at tiers t′ and t″ ≥ t′, is connected by a path containing grade-t′ or better (grade) edges. The MTT problem arises in the telecommunication setting (where we must choose between competing communication technologies) end in the transportation setting (where the cost incurred determines the type of access provided between two points). In this paper, we develop two solution approaches for the problem. We first develop a recursive heuristic for the MTT problem, and obtain data-independent bounds for MTT problems with 3-tiers. For one case, the bound on the performance ratio of the recursive heuristic is 1.52241. Next, we develop a dual-based solution procedure for this problem, and conduc...