咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >带基数约束的次模+超模(BP)函数最大化问题的流算法 收藏

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

Streaming algorithms for the maximization of submodular+supermodular functions with a cardinality constraint

作     者:连月芳 张真宁 赵中睿 堵丁柱 LIAN Yuefang;ZHANG Zhenning;ZHAO Zhongrui;DU Dingzhu

作者机构:北京工业大学数学学院运筹学与信息工程系 美国德克萨斯大学达拉斯分校计算机系 

出 版 物:《运筹学学报》 (Operations Research Transactions)

年 卷 期:2022年第26卷第1期

页      面:85-98页

核心收录:

学科分类:12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基  金:国家自然科学基金(Nos.12131003 12001025) 

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

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

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分