论文部分内容阅读
将通信网络扩张升级问题抽象为带约束的支撑树形图容量扩张问题（CEPAC），并针对该问题进行研究。首先，由0-1背包问题归约出CEPAC问题的实例，进而分析CEPAC问题的NP-困难性。其次，采用支撑树Megiddo参数搜索和拟阵交的Megiddo参数搜索策略，建立支撑树形图多面体与拟阵交之间的关系，将一棵最优支撑树形图通过基本变换转换成与之相邻的最优支撑树形图，为CEPAC问题设计一个（2, 1）-近似的带约束的拟阵交算法。最后，考虑最小支撑树形图容量扩张问题（CEPMA），并利用字典序方法对朱–刘算法进行改进求解CEPMA问题。