特定材料构建支撑树问题的近似算法研究

作者：何帅

来源：科技资讯, 2019, 17(16): 228-229.

DOI：10.16661/j.cnki.1672-3791.2019.16.228

• 支撑树
• 装箱
• NP—难
• 近似算法

结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w, c)和一种长度为L的特定材料,要在图G中寻找一颗支撑树,并用给定的材料来构建支撑树的边,支撑树的总构建费用包括材料费用和构建费用两部分,目标是使得总构建费用达到最小。该问题是NP—难的,不存在多项式时间算法,除非P=NP。该文对所提问题设计了一个2—近似算法,并分析了算法的复杂性,证明了算法的近似度。

• 单位
  昆明工业职业技术学院