带基数约束的次模+超模(BP)函数最大化问题的流算法

作者：连月芳; 张真宁^*; 赵中睿; 堵丁柱

来源：运筹学学报, 2022, 26(01): 85-98.

DOI：10.15960/j.cnki.issn.1007-6093.2022.01.006

• BP-函数最大化
• 全局曲率
• 边际收益递减率
• 流算法
• 基数约束

本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率(γ),我们设计了单轮读取数据的过滤-流算法,并结合次模、超模函数的全局曲率(κg)得到算法的近似比为min■。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出:次模函数和超模函数在同量级条件下,能保证在较少的时间内得到与贪婪算法相同的最优值。

• 单位
  数学学院; 北京工业大学