基于滑动窗口模型的非次模优化近似算法

作     者：罗允辛 

作者单位：天津理工大学 

学位级别：硕士

导师姓名：吴晨晨

授予年度：2022年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：流算法 非次模极大化 基数约束 滑动窗口 集合函数 

摘      要：本文主要针对带基数约束的非次模函数极大化问题进行研究,不同于以往的只插入型算法,本文主要基于滑动窗口的思想设计即可插入又可删除的双向算法,解决元素具有时效性且函数不满足次模性质的问题.在第一章,对本文所研究问题的价值进行阐述,并对问题介绍进行前情铺垫,将后文涉及到的定义定理及符号进行简要说明.在第二章,主要介绍了几类研究较为广泛的次模及非次模极大化问题.从不同角度阐述了每一类问题所研究的重点及其优缺点,并简要叙述了解决该类问题所用到的基本思想.在第三章,首先对本文所要研究的问题进行描述,为了很好的解决问题,选择采用滑动窗口的思想,对过期元素进行筛选,再对筛选后的元素运用筛流算法以达到预期目标.其次对算法进行了详细的阐述,并从近似比,存储复杂度,时间复杂度等方面分析算法性能.为了获得更好的近似比,我们以舍弃一部分存储为代价,设计了双向子窗口算法,最后从近似比,存储复杂度,时间复杂度等方面分析算法性能.