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

摘要：

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

关键词：独立系统、下模函数、拟阵交构、邻域算法

分类号：O224(运筹学)

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

页数：共3页

页码：6-8