摘要：近几十年来，数据以流模型的方式传输的情况收到了大量的关注。在提取海量流数据信息的过程中，出现了受基数约束的非次模集函数最大化问题。然而事实上，对于非次模函数的最大值，要想求解其精确值是非常困难的，人们很难在多项式时间内得到它的精确解。但是这些非次模优化问题的广泛应用又使其求解成为必须。因此，对应的方法之一就是牺牲精度来换取时间，即在多项式时间内得到问题的一个近似解，这便是近似算法。在本文中，我们研究在流模型下求解单调非次模集函数的函数最大值。我们改进了之前已有算法的系数，从而将原有的结果进行改进，并且在理论上得到了更好的近似比。

关键词：流模型、近似算法、非次模、基数约束、集函数

目录

摘要

Abstract

1 绪论-3

1.1 研究背景-3

1.2 研究意义-3

1.3 研究现状-3

1.4 问题提出-4

2 基本定义-5

3 算法设计-7

3.1 算法1：已知最优值的算法-7

3.2 算法2：已知最大单例值的算法-10

3.3 算法3：更新近似最优值候选集的算法-11

4 结论-14

谢 辞-15

参考文献-16