多材料Terminal Steiner树拼接问题的近似算法研究

文永松 朱淑娟 庞一成

摘  要： 在赋权连通网络下，给定多种材料及每种材料的费用和拼接费用，以便寻找赋权网络中的一棵Terminal Steiner树，并用给定材料连接此树，使得总费用及材料根数达到最小，记此问题为多材料Terminal Steiner树拼接问题。为了解决Terminal Steiner树拼接问题，首先分析Terminal Steiner 树拼接问题是NP问题，不存在多项式时间算法;然后基于Steiner 树问题和变尺寸装箱问题的近似算法及算法复杂度，给出多材料的Terminal Steiner树拼接问题的一个近似算法;最后证明算法的近似值及近似算法的时间复杂度。

关键词： Terminal Steiner树; 拼接问题; 变尺寸装箱; 近似算法; 绝对近似比; 时间复杂度

中图分类号： TN911?34; TP301.6               文献标识码： A                    文章编号： 1004?373X（2018）10?0028?03

Abstract： In the weighted and connected network， a variety of materials， cost of each material， and the splicing cost are given to look for a Terminal Steiner tree in the weighted network. The given materials are used to connect the Terminal Steiner tree， so as to minimize the total cost and the number of materials. This can be called the multi?material Terminal Steiner tree splicing problem. The Terminal Steiner tree splicing problem is analyzed and determined to be the NP problem， in which the polynomial time algorithm does not exist， and then an approximation algorithm of the multi?material Terminal Steiner tree splicing problem is presented based on the approximation algorithm of Steiner tree problem and variable?sized bin packing problem as well as the complexity of the algorithm， so as to resolve the Terminal Steiner tree splicing problem. The approximate value of the algorithm and the time complexity of the approximation algorithm are demonstrated.

Keywords： Terminal Steiner tree; splicing problem; variable?sized bin packing; approximation algorithm; absolute approximate ratio; time complexity

考虑这样一个实际问题：假设某一军事地区有多个信号站点，这些站点可以分为两大类，一类为必需的信号站点，另一类是辅助信号站点，且必需的信号站点作为叶子节点与某几个辅助信号站点终端相连接。为了保证信号的联通性，需要一些不同特殊的材料把必需的信号站点与辅助信号站点拼接起来，费用包括拼接费用和材料费用两部分。由于选取的辅助信号站点的不同，从而使连接信号站点之间的方式有许多种，每种方式的拼接费用和所需的材料费用可能不同，因此，最终所产生的总费用也不尽相同，在拼接时，人们总是希望费用及材料数目尽可能的少一些。为了解决该问题，把各信号站点看成网络中的顶点，线路看成网络中的，从而将该问题抽象成为一个组合最优化问题。文中用Terminal Steiner 树问题及装箱问题来解决该优化问题。

Terminal Steiner树问题源于Steiner树问题，文献[1]证明了Terminal Steiner 树问题是NP?难，给出了绝对近似比为2+k的近似算法，k为Steiner树问题的最好的绝对近似比;文献[2?5]讨论了Terminal Steiner树问题的其他较好的近似算法;变尺寸装箱问题是一维装箱问题的推广，文献[6]证明了变尺寸装箱问题是NP?难，给出了最坏情况下2，[32]，[43]的渐近近似算法;文献[6?9]给出了变尺寸装箱问题其他渐进近似算法的结果;文献[10?11]分别讨论了单个材料在树形结构网络构建问题及有向图中满足某种结构的构建问题，本文基于Terminal Steiner树问题算法及变尺寸装箱问题算法的基础上，设计了多材料Terminal Steiner树拼接问题的一个近似算法。

3  结  论

Terminal Steiner树问题在通信工程以及超规模集成电路设计（VLSI）上有着普遍的应用[12]。本文基于Terminal Steiner树问题和变尺寸装箱问题的相关算法，提出网络中多材料Terminal Steiner树的拼接问题。本文设计了该问题[2ρ]?绝对近似算法，算法使用材料的方案是由变尺寸装箱问题所决定的，材料的多少依赖于变尺寸装箱问题的近似比。取文献[13]中Steiner树的绝对近似比[m=1.55]，文献[2]中Terminal Steiner树的绝对近似比[ρ=2m]，则多材料Terminal Steiner Tree 拼接问题的绝对近似比为6.1。算法精度的提高很大程度上依赖于Terminal Steiner 树问题的近似值，因此，要提高算法的精度只需要改进Terminal Steiner 树算法的精度。

参考文献

[1] LIN G， XUE G. On the Terminal Steiner tree problem [J]. Information processing letters， 2002， 84（2）： 103?107.

[2] DRAKE D E， HOUGARDY S. On approximation algorithms for the Terminal Steiner tree problem [J]. Information processing letters， 2004， 89（1）： 15?18.

[3] MARTINEZ F V， PINA J C D， SOARES J. Algorithms for Terminal Steiner tree [C]// Proceedings of International Computing and Combinatorics Conference. Berlin： Springer， 2005： 369?379.

[4] CHEN Y H. An improved approximation algorithm for the Terminal Steiner tree problem [C]// Proceedings of International Conference on Computational Science and Its Applications. Berlin： Springer， 2011： 141?151.

[5] LEE C W， HUANG C W， PI W H， et al. An improved approximation ratio to the partial?Terminal Steiner tree problem [J]. IEEE transactions on computers， 2014， 64（1）： 274?279.

[6] FRIESEN D K， LANGSTON M A. Variable sized bin packing [J]. SIAM journal on computing， 1986， 15（1）： 222?230.

[7] KANG J， PARK S. Algorithms for the variable sized bin packing problem [J]. European journal of operational research， 2003， 147（2）： 365?372.

[8] EPSTEIN L， LEVIN A. An APTAS for generalized cost variable?sized bin packing [J]. SIAM journal on computing， 2008， 38（1）： 411?428.

[9] JANSEN K， KRAFT S. An improved approximation scheme for variable?sized bin packing [J]. Theory of computing systems， 2016， 59（2）： 262?322.

[10] LI J， GE Y， HE S， et al. Approximation algorithms for constructing some required structures in digraphs [J]. European journal of operational research， 2014， 232（2）： 307?314.

[11] LI J， Guan L， DING H， et al. Approximations for constructing tree?form structures using specific material with fixed length [J]. Optimization letters， 2016， 10（6）： 1?9.

[12] VAZIRANI V V. Approximation algorithm [M]. Berlin： Springer， 2010.

[13] ZELIKOVSKY A Z. A faster approximation algorithm for the Steiner tree problem in graphs [J]. Information processing letters， 1993， 46（2）： 79?83.

[14] KOU L， MARKOWSKY G， BERMAN L. A fast algorithm for Steiner trees [J]. Acta informatica， 1981， 15（2）： 141?145.