摘要：近幾十年來，數據以流模型的方式傳輸的情況收到了大量的關注。在提取海量流數據信息的過程中，出現了受基數約束的非次模集函數最大化問題。然而事實上，對于非次模函數的最大值，要想求解其精確值是非常困難的，人們很難在多項式時間內得到它的精確解。但是這些非次模優化問題的廣泛應用又使其求解成為必須。因此，對應的方法之一就是犧牲精度來換取時間，即在多項式時間內得到問題的一個近似解，這便是近似算法。在本文中，我們研究在流模型下求解單調非次模集函數的函數最大值。我們改進了之前已有算法的系數，從而將原有的結果進行改進，并且在理論上得到了更好的近似比。

關鍵詞：流模型、近似算法、非次模、基數約束、集函數

目錄

摘要

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