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

Approximation Algorithm and Its Performance for Maximizing Submodular Function Subject to Matroid Intersection

作　　者：张立群[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《淮海工学院学报（自然科学版）》2014年第4期6-8,共3页Journal of Huaihai Institute of Technology:Natural Sciences Edition

摘　　要：下模函数的最大值问题是组合优化中的核心问题,然而求解下模函数最大值问题是一个NP-难问题,故人们降低要求,求解它的最优近似解.在拟阵约束的基础上,进一步研究拟阵交构成的独立系统下求解下模函数最大值问题,运用了近似领域算法,得到下模函数的近似最优解,并讨论给出了近似算法的性能分析,得出近似解的近似度≤(αm+1).The maximum value of submodular function is a key problem in combinatorial optimiza-tion;however,the unavailability of the solution to the NP-Hard problem makes people take a step back to solve its optimal approximate value.Based on matroid constraints,a further research was done in this paper on matroid intersection under an independent system to solve the maximum value of submodular function.The approximate algorithm method was used to get its approxi-mate optimal solution.Also,the approximation performance was discussed and put forward to get the degree of approximation of approximate solution≤（αm＋1）.

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

分 类 号：O224[理学—运筹学与控制论]