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

摘要：

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

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

所属期刊栏目：41

分类号：TN911-34;TP301.6

资助基金：国家自然科学基金11761018;贵州省科学技术基金J[2015]2026Project Supported by National Natural Science Foundation of China11761018;Science and Technology Foundation of Guizhou ProvinceJ[2015]2026

在线出版日期：2018-06-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：28-30