两个拟阵交的一种推广—交拟阵

针对一类比两个拟阵交更广泛的独立系统——交拟阵,本文探讨了它的某些性质;证明了:任一交拟阵是(2,2)-系统。从而,初步解决了如何在多项式时间内找到一给定交拟阵的最大独立集问题。

拟阵交约束分划

给出了用求最大重量拟阵交算法来求定形拟阵交 2 分划问题的最优解的一个充分条件 .

拟阵交构约束的下模函数最大值问题的近似算法及其分析

下模函数的最大值问题是组合优化中的核心问题,然而求解下模函数最大值问题是一个NP-难问题,故人们降低要求,求解它的最优近似解.在拟阵约束的基础上,进一步研究拟阵交构成的独立系统下求解下模函数最大值问题,运用了近似领域算法,得到下模函数的近似最优解,并讨论给出了近似算法的性能分析,得出近似解的近似度≤(αm+1).

带约束的支撑树形图容量扩张问题

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