论文部分内容阅读
结合最小k度限制树和一维装箱这两个问题,本文研究了一个新的最优化问题:给定一个简单的连通无向网络G=(V,E;w)及常数L。我们用长度为"L"的材料构建k度限制树T,且T上的每条边至多能用一次料头(指材料构建完某条边后剩下的部分)。假设所用材料的根数为C,目标是C尽可能小。本论文对所提问题的特殊情形设计了一个3/2近似算法,对一般情形设计了一个2-近似算法,接着将2-近似算法改进到7/4-渐进近似。