摘要
为了从数据流中抽取满足某些条件的子集,使得其目标函数的值尽可能的大,提高多项式更新时间,研究了从大规模数据集G(称为基集)中选择一个子集S来表示整个数据集的问题.通过提前设置阀值改进原有算法的系数,分别设计了更新近似最优值候选集的算法、已知最大单例值的算法和已知最优值的算法,在流模型下求解单调非次模集函数的函数最大值及其近似比.结果表明,改进了3种利用递减收益率的算法在理论上得到了更好的近似比.
In order to extract subsets that meet certain conditions from the data stream,make the value of its objective function as large as possible,and improve the polynomial update time,the problem of selecting a subset from a large dataset(called a base set)to represent the entire dataset is studied.By setting the threshold in advance to improve the coefficients of the original algorithm,the algorithm to update the candidate set of approximate optimal values,the algorithm to know the maximum single case value and the algorithm to know the optimal value are designed respectively,and the function maximum and its approximate ratio of the monotone non sub modular set function are solved under the flow model.The results show that the improved three algorithms using diminishing returns get better approximation ratio in theory.
作者
耿红梅
Geng Hongmei(Yangzhou Polytechnic Institute)
出处
《哈尔滨师范大学自然科学学报》
CAS
2023年第2期1-5,共5页
Natural Science Journal of Harbin Normal University
基金
国家自然科学基金项目(5217040363)
关键词
流模型
近似算法
基数约束
集函数
Flow model
Approximation algorithm
Cardinal constraint
Set function
