K-拟阵交约束下单调γ-次模函数最大化问题研究

作者：李娜; 方奇志^*; 曲晓英

来源：中国海洋大学学报(自然科学版), 2021, 51(S1): 101-107.

DOI：10.16441/j.cnki.hdxb.20200181

• 函数最大化
• γ-次模函数
• 拟阵
• K-拟阵交
• 局部搜索算法
• 交换性质

次模函数最大化问题是有向图最大割问题、设施选址最大化问题等问题的一般化,是组合优化中的核心问题,次模率γ(0≤γ≤1)是一种刻画集合函数次模性的度量。本文通过拟阵交换性质的刻画,利用局部搜索算法,研究了K-拟阵交约束下非负单调γ-次模函数最大化问题,得到如下结论:对任意的K≥2,δ>0,存在求解K-拟阵交约束下非负单调γ-次模函数最大化问题的多项式时间算法,近似比为■为实参数。当γ=1时(即目标函数为次模函数),与Nong等给出的近似比■相比,本文得到更好的近似比■。此外,本文还将次模函数的两个性质推广到γ-次模函数。

• 出版日期2021
• 单位中国海洋大学