Matriod & Greedy 拟阵与贪心

最大生成树（引入）

最大生成树问题是指以下问题：

输入：图 $G=(V,E)$，和边权 $w \in \mathbb{Z}^{E}_{> 0}$

输出：图 $G$ 的一颗生成树 $F$，满足 $F$ 中的边权值和最大

Kruskal 算法

众所周知，Kruskal 算法可以求解最大生成树问题，算法流程如下：

$$\begin{aligned} &\textbf{function}\space \text{Kruskal(} V,E,w\text{)} \\ &\qquad F \leftarrow \emptyset \\ &\qquad \text{sort edges in }E\text{ in non-increasing order of weights }w \\ &\qquad \textbf{for} \text{ each edge }(u,v) \text{in the order } \textbf{do} \\ &\qquad \qquad \textbf{if} \space F \cup \{(u,v)\} \text{ do not contain a cycle } \space\textbf{then} \\ &\qquad \qquad \qquad F \leftarrow F \cup \{(u,v)\} \\ &\qquad \textbf{return}\space F \end{aligned}$$

给函数传入一张图，返回值即为图 $G = (V,E)$ 的一颗最大生成树。这是一个典型的贪心算法，接下来证明它的正确性。在此之前，需要引入一个新的问题辅助证明。

带有预选边的最大生成树问题

输入：图 $G=(V,E)$，和边权 $w \in \mathbb{Z}^{E}_{> 0}$，以及一个集合 $F_0 \subseteq E$，保证 $F_0$ 中的边不构成环

输出：图 $G$ 的一颗生成树 $F$，满足在 $F_0 \subseteq F$ 的条件下 $F$ 中的边权值和最大

容易发现，这就是 Kruskal 算法运行过程中得到的子问题。

引理 1.1：对任意的带有预选边的最大生成树问题（用 $G=(V,E),w,F_0$ 描述），令 $e^*$ 表示边集 $E \setminus F_0$ 中满足 $\{e^*\} \cup F_0$ 不包含环的权值最大的边。则一定存在一个最优解 $F_T$ 满足 $e^* \in F_T$。

证明：任取一最优解 $F_T’$，若 $e^* \not \in F_T’$，则 $F_T’ \cup e^*$ 有环。取出环的边集 $C$，则 $e^* \in C$。容易发现，删掉任意的 $e \in C$ 均会得到一棵树。由于引理中假设，$e^*$ 权值最大，则一定存在 $e \in C,e \neq e^*, w_e = w_{e^*}$（否则与 $F_T’$ 为最优解矛盾），于是删去 $e$ 并加入 $e^*$ 得到仍然是生成树，且权值和与 $F_T’$ 相同，仍为最优解。 $\square$

根据 引理 1.1 可以归纳证明，Kruskal 算法总能得到最优解。

拟阵

更一般化的问题

将最大生成树问题一般化：

输入：集合 $E$ 表示元素的集合，$w \in \mathbb{Z}^E_{>0}$ 表示每个元素的权值，隐式给出 $\mathcal{I}$，表示 $E$ 的某些子集构成的集合，且满足

• $\emptyset \in \mathcal{I}$
• $\mathcal{I}$ 具有 遗传性：$\forall A \in \mathcal{I},B \subsetneq A: B \in \mathcal{I}$

输出：集合 $S \in \mathcal{I}$，使得 $\sum\limits_{e \in S} w_e$ 最大。

如果定义 $E$ 表示图的边集，$\mathcal{I}$ 表示 $E$ 的满足边不成环的子集（即 $E$ 中能构成森林的子集），则上述问题就是 最大生成树 问题。

于是我们可以依照 Kruskal 算法的流程，写出以下贪心算法：

$$\begin{aligned} &\textbf{function}\space \text{Greedy(} E,\mathcal{I},w\text{)} \\ &\qquad F \leftarrow \emptyset \\ &\qquad \text{sort elements in }E\text{ in non-increasing order of weights }w \\ &\qquad \textbf{for} \text{ each element }e \text{ in the order } \textbf{do} \\ &\qquad \qquad \textbf{if} \space F \cup \{e\} \in \mathcal{I} \space\textbf{then} \\ &\qquad \qquad \qquad F \leftarrow F \cup \{e\} \\ &\qquad \textbf{return}\space F \end{aligned}$$

但是这个算法总是能解决这个更一般的问题吗？答案是否定的，反例就是 背包问题：

输入：集合 $E$ 表示元素的集合，$w \in \mathbb{Z}^E_{>0}$ 表示每个元素的权值，$c \in \mathbb{Z}^E_{>0}$ 表示每个元素的重量，限制 $C$。

输出：集合 $S \in E$，使得在满足 $\sum\limits_{e \in S} c_e \le C$ 的条件下 $\sum\limits_{e \in S} w_e$ 最大。

通过指定 $\mathcal{I}$ 表示满足 $\sum\limits_{e \in S} c_e \le C$ 的 $E$ 的子集，显然 $\mathcal{I}$ 满足遗传性，且 $\emptyset \in \mathcal{I}$。

但是在 $w = \{10,9,9\}, c = \{11,5,5\}, C = 10$ 时，$\text{Greedy(} E,\mathcal{I},w\text{)}$ 并没有返回最优解，因为在取完第一个元素后，背包就装不下后两个元素了，而显然取后两个会更优。

事实上，我们知道，背包问题需要通过更为复杂的动态规划算法才能在伪多项式时间内得到最优解。

类似的问题还有很多，例如二分图最大匹配问题，一般图的最大权独立集问题等，其中前者可以用最大流算法在多项式时间内求解，而后者是 NP-Hard 的，我们认为它不应该存在多项式时间解法。

贪心法能得到最优解的问题

拟阵 描述了一系列能用贪心法得到最优解的问题。

定义：一个拟阵 $\mathcal{M}$ 是个二元组 $(E, \mathcal{I})$，其中 $E$ 是一个有穷集合，称为 ground set，$\mathcal{I}$ 是 $E$ 的子集的一个集合（即 $\mathcal{I} \subseteq 2^E$），称为 独立集，且 $\mathcal{I}$ 满足以下性质：

• $\emptyset \in \mathcal{I}$
• $\mathcal{I}$ 具有 遗传性：$\forall A \in \mathcal{I},B \subsetneq A: B \in \mathcal{I}$
• $\mathcal{I}$ 具有 交换性（又称 增广性）：若 $A, B \in \mathcal{I}, |B| < |A|$，则一定存在一个 $e \in A \setminus B$ 使得 $B \cup \{e\} \in \mathcal{I}$。

图拟阵：对图 $G=(V,E)$，$S \in \mathcal{I}$ 当且仅当 $(V,S)$ 中没有环（构成森林）。此时 $(E,\mathcal{I})$ 构成一个拟阵，称它为图拟阵。

证明图拟阵：前两条性质显然，只证交换性。因为 $|B| < |A|$，则 $(V,B)$ 比 $(V,A)$ 包含更多的连通块（每条边会使连通块数量减一），于是一定存在一条边 $e \in A \setminus B$，使得 $e$ 连接了 $(V,B)$ 中的两个不同连通块，即加入 $e$ 不会使 $(V,B \cup \{e\})$ 中有环。 $\square$

于是最大生成树问题可以用贪心法求解。

背包问题不能用拟阵描述：构造反例：若 $c = \{1,1,2\},C = 2$，则有 $\{1,2\},\{3\} \in \mathcal{I}$，但此时 $\{1,3\},\{1,2\} \not\in \mathcal{I}$，不满足交换性。

二分图最大匹配问题同样可以找出不满足交换性的反例。

于是可以提出：

定理 1：贪心法能正确求出拟阵的最大权独立集。

要证明这个定理，可以类似证明 Kruskal 算法正确性的方法，先找出贪心算法运行中的一个状态，证明其不会错过最优解：

引理 1.2：给定拟阵 $\mathcal{M} = (E, \mathcal{I})$，权值 $w \in \mathbb{Z}^{E}_{>0}$，当前决策 $S \in \mathcal{I}$，定义最优解为满足 $S \subseteq F$ 且 $\sum_{i \in F} w_i$ 最大的任意一个 $F$，找出一个 $e^*$ 满足 $e^* \in E \setminus S, \{S \cup \{e\}\} \in \mathcal{I}$，使得 $w_{e^*}$ 最大。那么一定存在一个最优解 $F$ 满足 $e^* \in F$。

证明：令 $F$ 为任一最优解，若 $\forall F:e^* \in F$，则 引理 1.2 成立。
否则取出 $F’$ 满足 $e^* \not \in F’$。

令 $S’ = S \cup \{e^*\}$，重复以下过程直到 $|S’| = |F’|$（由于 $w \in \mathbb{Z}^{E}_{>0}$，于是一定有 $|S| < |F’|$）：

• 找出任一 $e \in F’ \setminus S’$，满足 $\{e\} \cup S’ \in \mathcal{I}$，根据交换性，$e$ 一定存在。
• 将 $S’$ 赋值为 $S’ \cup \{e\}$

由上述过程可知，$S’$ 与 $F’$ 大小相同，且有且仅有一个元素不同，且不同的两元素其一为 $e^*$，设另一个为 $e’$。由于 引理 1.2 中假设 $e^*$ 为合法的元素中权值最大的一个，于是一定有 $w_{e^*} \ge w_{e’}$，而因为 $F’$ 是最优解，于是只能取 $w_{e^*} = w_{e’}$，于是 $S’$ 同样是最优解，且满足 $e^* \in S’$。 $\square$

据 引理 1.2 容易归纳证明 定理 1。

拟阵与线性代数

（据说这也是拟阵得名的一个原因）

定义 线性拟阵：$\mathcal{M} = (E,\mathcal{I})$：对每个 $e \in E$，都有一个向量 $\vec{v_e} \in \mathbb{R}^{d}$ 与之对应。且 $\mathcal{I} = \{S \in E: \{\vec{v_e}\}_{e \in S} \text{ are linearly independet}\}$。

linearly independet 即线性无关，指向量集合中任意一个向量不能被其余向量线性表出。

可以发现，图拟阵能转化成线性拟阵，具体的：对每条边 $(u,v) \in E$，令向量 $\vec{v_e} \in \mathbb{R}^{|V|}$ 在第 $u$ 维填 $1$，第 $v$ 维填 $-1$，其余维填 $0$，则无环等价于边集对应的向量集合线性无关。

同时可以发现，均匀拟阵，划分拟阵等均可转化为线性拟阵。

更多定义

定义拟阵 $\mathcal{M} = (E,\mathcal{I})$ 的 基 为极大独立集，拟阵的 环 为极小非独立集，或者说：

• 对于一个 基 $\mathcal{B}$，满足 $\mathcal{B} \in \mathcal{I}$ 且 $\forall e \in E \setminus \mathcal{B}:\mathcal{B} \cup \{e\} \not \in \mathcal{I}$。

• 对于一个 环 $\mathcal{C}$，满足 $\mathcal{C} \not\in \mathcal{I}$ 且 $\forall e \in \mathcal{C}: \mathcal{C} \setminus \{e\} \in \mathcal{I}$。

引理 1.3.1：拟阵中所有的基大小相同，且均为最大独立集。

证明：若两个基大小不同，则可以根据拟阵的交换性使得较小的基增大，这与基的定义矛盾。

据 引理 1.3.1 可以定义拟阵的 秩 为拟阵的最大独立集大小，或是任意一个基的大小。

同时定义 秩函数 $r(S)$ 表示 $S$ 的最大独立集大小，其中 $S \in E$，类似的，称 $r(S)$ 为 $S$ 的 秩。

于是可以得出秩一些的性质：

• $0 \le r(S) \le |S|$。
• $r(\emptyset) = 0$。
• 若 $S \subseteq T$，则有 $r(S) \le r(T)$。
• $r$ 是次模的。

对第 $4$ 条，令 $n \in \mathbb{Z}_{>0}$，则 $f: 2^{[n]} \rightarrow \mathbb{R}$ 是次模（submodular）的，当且仅当以下三个条件任意一条成立：

• $\forall A,B \in [n]: f(A \cup B) + f(A \cap B) \le f(A) + f(B)$。
• $\forall A \subseteq B \subsetneq [n]: f(B \cup \{i\}) – f(B) \le f(A \cup \{i\}) – f(A)$。
• $\forall A \subseteq [n];i,j \in [n] \setminus A,i \neq j: f(A \cup \{i,j\}) + f(A) \le f(A \cup \{i\}) + f(A \cup \{j\})$

（其实三个条件是等价的，从任意一个都可以推出另外两个）

把不等号反向即可得到 超模（supermodular）的定义。

拟阵的运算

咕咕咕

Greedy & Approximation Algorithms 近似算法与贪心

最小点覆盖问题

定义图 $G=(V,E)$ 的点覆盖为点集 $V$ 的一个子集 $S$，满足 $\forall (u,v) \in E: u \in S \vee v \in S$。

据此给出最小点覆盖问题：

输入：图 $G=(V,E)$

输出：图的最小点覆盖 $S$

对这个问题，显然是无法构造拟阵的。当然，最小点覆盖问题是 NP-Complete 的，我们认为它不应该存在多项式时间的算法。

既然如此，我们希望得出一个近似算法，以此求出一个尽可能接近最优解的近似解。容易想到的一个近似算法就是贪心法。

最小点覆盖问题的贪心法

我们尝试直接把求解拟阵最大权独立集的贪心算法套用过来：

$$\begin{aligned} &\textbf{function}\space \text{VertexCover(} V,E\text{)} \\ &\qquad F \leftarrow \emptyset, E’ \leftarrow E \\ &\qquad \textbf{while} \space E’ \neq \emptyset \space \textbf{do} \\ &\qquad \qquad \text{find } u \in E’ \text{ which has the maximum degree}\\ &\qquad \qquad F \leftarrow F \cup \{u\} \\ &\qquad \qquad \text{remove all edges incident to } v \text{from } E’\\ &\qquad \textbf{return}\space F \end{aligned}$$

即每次找出度数最大的节点，将它加入点覆盖，并删去和它相连的所有边，直到边集为空。容易发现，返回值 $F$ 一定是原图的一个点覆盖。

定理 2.1.1：$\text{VertexCover(} V,E\text{)}$ 是一个 $(\ln n + 1)$ 倍近似的算法（近似比不超过 $(\ln n + 1)$）。

证明：在之后更一般的问题下有证（定理 2.2.2）。

在绝大部分随机数据下，这个算法表现很优秀，当然，你可以构造一些数据（比如一个二分图，左边顶点集合中的点的度数相同，右边顶点集合中的点的度数不相同），使得它的近似比超过 $2$ ，这就使得它劣于接下来的算法。

$\text{Greedy(} V,E\text{)}$ 的近似比随数据规模增大而增大，我们希望获得一个近似比与数据规模无关的算法。

接下来提出一个具有常数近似比的最小点覆盖算法：

$$\begin{aligned} &\textbf{function}\space \text{VertexCover2(} V,E\text{)} \\ &\qquad F \leftarrow \emptyset, E’ \leftarrow E \\ &\qquad \textbf{while} \space E’ \neq \emptyset \space \textbf{do} \\ &\qquad \qquad \text{let } (u,v) \text{ be any edge in }E’\\ &\qquad \qquad F \leftarrow F \cup \{u,v\} \\ &\qquad \qquad \text{remove all edges incident to } u \text{ and } v \text{ from } E’ \\ &\qquad \textbf{return}\space F \end{aligned}$$

看起来比上面那个还 naive

定理 2.1.2 $\text{VertexCover2(} V,E\text{)}$ 是一个 $2$ 倍近似的算法。

证明：对于每条被考虑到的边 $(u,v)$，发现它们构成一个匹配，于是最优解至少需要选择它们的一半。

最小集合覆盖问题

将点覆盖一般化可以得到以下问题：

输入：集合 $\mathbb{U}$ 满足 $|\mathbb{U}| = n$；$m$ 个集合 $S_1, S_2 ,\dots, S_m \in \mathbb{U}$。

输出：最小的集合 $F \in [m]$，满足 $\bigcup\limits_{i \in F} S_i = \mathbb{U}$。

即最小集合覆盖问题，这个问题还没有常数近似比的贪心法。

有频率限制的最小集合覆盖问题

若给上述问题添加一个条件，即频率限制，可以得到以下问题：

输入：集合 $\mathbb{U}$ 满足 $|\mathbb{U}| = n$；$m$ 个集合 $S_1, S_2 ,\dots, S_m \in \mathbb{U}$。频率 $f$，满足 $\forall j \in \mathbb{U}$，$j$ 至多在 $f$ 个 $\{S_1, S_2, \dots, S_m\}$ 中出现。

输出：最小的集合 $F \in [m]$，满足 $\bigcup\limits_{i \in F} S_i = \mathbb{U}$。

容易发现，最小点覆盖问题其实是频率限制 $f = 2$ 的最小集合覆盖问题。

于是类似最小点覆盖问题的 $2$ 倍近似贪心法，可以得到以下算法：

$$\begin{aligned} &\textbf{function}\space \text{SetCoverF(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}, f\text{)} \\ &\qquad F \leftarrow \emptyset \\ &\qquad \textbf{while} \space \bigcup\limits_{i \in F} S_i \neq \mathbb{U} \space \textbf{do} \\ &\qquad \qquad \text{let } e \text{ be any element in } \mathbb{U} \setminus \bigcup\limits_{i \in F} S_i\\ &\qquad \qquad F \leftarrow F \cup \{i \in [m]: e \in S_i\} \\ &\qquad \textbf{return}\space F \end{aligned}$$

定理 2.2.1：$\text{SetCoverF(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}, f\text{)}$ 是一个 $f$ 倍近似算法。

证明：令 $U$ 为所有被考虑到的 $e$ 的集合，可以发现，不存在集合 $S_i$，使得 $S_i$ 包含 $U$ 中的两个元素。那么最优解需要 $|U|$ 个集合，而这个算法选择了至多 $f \times |U|$ 个集合，于是它是 $f$ 倍近似的。$\square$

一般的集合覆盖问题

现在没有了 $f$ 的限制，继续套用 $\text{SetCoverF(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}, f\text{)}$ 只能得到 $n$ 倍近似的答案，这显然不优。不过刚才在最小点覆盖问题我们还提出了一个 $(\ln n + 1)$ 倍近似的算法，现在试着把它套用到这个更一般的问题上：

$$\begin{aligned} &\textbf{function}\space \text{SetCover(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}\text{)} \\ &\qquad F \leftarrow \emptyset, U \leftarrow \emptyset \\ &\qquad \textbf{while} \space U \neq \emptyset \space \textbf{do} \\ &\qquad \qquad \text{find } i \text{ which maximize } |U \cap S_i| \\ &\qquad \qquad F \leftarrow F \cup \{i\},U \leftarrow U \setminus S_i \\ &\qquad \textbf{return}\space F \end{aligned}$$

接下来证明这个算法的近似比。

令 $G$ 为一个最优解，$g = |G|$。

引理 2.2.1：令 $F_t, t \in \mathbb{Z}_{\ge 0}$ 表示在 $\textbf{while}$ 循环进行 $t$ 次后，得到的集合 $F$，令 $f_t = |\mathbb{U} \setminus F_t|$，即在 $t$ 次循环后未覆盖的元素的数量。于是 $\forall t \ge 1: f_t \le \left(1 – \dfrac{1}{g}\right) f_{t-1}$。

证明：令 $G^*_1, G^*_2, \dots, G^*_g$ 表示 $G$ 选中的集合，因为集合覆盖的要求可得：$G^*_1 \cup G^*_2 \cup \dots \cup G^*_g = \mathbb{U}$

。未覆盖的元素有 $f_{t-1}$ 个，而集合有 $g$ 个，根据抽屉原理，$G^*_1, G^*_2, \dots, G^*_g$ 中一定存在一个集合 $G^*_i$，满足其中包含至少 $\left\lceil \dfrac{f_{t-1}}{g} \right\rceil$ 个未覆盖元素。

由于上述算法会选择能最大化 $|U \cap S_i|$ 的集合，因此有 $f_t \le f_{t-1} – \dfrac{f_{t-1}}{g} = \left(1 – \dfrac{1}{g}\right) f_{t-1}$。$\square$

根据这个不等式，可以提出：

定理 2.2.2：$\text{SetCover(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}\text{)}$ 是一个 $(\ln n + 1)$ 倍近似的算法。

证明：显然有 $f_0 = n$，根据 引理 2.2.1 可得：$f_t \le \left(1 – \dfrac{1}{g}\right)^t n$。

令 $t = \lceil g \ln n \rceil$ 可得：$f_t \le \left(1 – \dfrac{1}{g}\right)^{g \ln n} n < n e^{- \ln n} = n \times \dfrac{1}{n} = 1$。

由于 $f_t \in \mathbb{Z}_{\ge 0}$，于是 $f_t = 0$。

因此 $\dfrac{|F|}{g} \le \dfrac{\lceil g \ln n \rceil}{g} \le \ln n + 1$，即这个算法的近似比为 $\ln n + 1$。 $\square$

最大覆盖问题

上面是一个典型的最小化问题，接下来研究最大化问题的近似算法，以最大覆盖问题为例。

输入：集合 $\mathbb{U}$，满足 $|\mathbb{U}|$；集合 $S_1, S_2, \dots, S_m \subseteq \mathbb{U}$；$k \in [m]$。

输出：$F \subseteq [m]$ 满足 $|F| = k$ 且最大化 $\left|\bigcup\limits_{i \in F} S_i\right|$

容易发现，这其实是最小集合覆盖问题的对偶问题，两个问题通过二分答案可以相互转化。

贪心法

仍然用类似 $\text{SetCover(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}\text{)}$ 的方法：

$$\begin{aligned} &\textbf{function}\space \text{MaximumCoverage(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}, k\text{)} \\ &\qquad F \leftarrow \emptyset, U \leftarrow \emptyset \\ &\qquad \textbf{for} \space t \leftarrow 1 \space \textbf{to} \space k \space \textbf{do} \\ &\qquad \qquad \text{find } i \text{ which maximize } |U \cap S_i| \\ &\qquad \qquad F \leftarrow F \cup \{i\},U \leftarrow U \setminus S_i \\ &\qquad \textbf{return}\space F \end{aligned}$$

定理 2.3.1：$\text{MaximumCoverage(} \mathbb{U}, \{S_1, S_2, \dots, S_m\}, k\text{)}$ 是一个 $\left(1 – \dfrac{1}{e}\right)$ 倍近似算法。

证明：令 $G$ 为一个最优解，$g = \left|\bigcup\limits_{i \in G} S_i \right|$，即最优解覆盖的元素个数。类似的，令 $f_t$ 表示 $t$ 次循环后，上述算法得到的 $F$ 覆盖的元素个数（$f_t = \left|\bigcup\limits_{i \in F_t} S_i \right|$）。

在第 $t$ 轮循环前（$t \ge 1$），已经覆盖 $f_{t-1}$ 个元素，于是最优解覆盖的元素中，至多有 $f_{t-1}$ 个被覆盖，即最少余下 $g – f_{t-1}$ 个元素未被覆盖。

根据抽屉原理，一定存在一个 $i \in G$，使得 $S_i$ 中有至少 $\left\lceil\dfrac{g – f_{t-1}}{k}\right\rceil$ 个元素未被覆盖。

上述算法的决策不会劣于这个结果，于是有 $f_t \ge f_{t-1} + \dfrac{g – f_{t-1}}{k}$。化简得到 $g – f_t \le \left(1 – \dfrac{1}{k}\right) (g – f_{t-1})$。

因为 $f_0 = 0$，于是有 $g – f_k \le \left(1 – \dfrac{1}{k}\right)^k (g – f_0) \le \dfrac{1}{e} (g – f_0) = \dfrac{g}{e}$。

移项可得：$f_k \ge \left(1 – \dfrac{1}{e}\right) g$，即算法的近似比为 $\left(1 – \dfrac{1}{e}\right)$。 $\square$

最大化次模函数

（这也是上面对贪心算法的讨论的终极目标，次模函数的定义在 拟阵与线性代数 部分已经给出）

次模函数 具有类似 边际收益递减规律 的性质，即在拥有的越多时，得到新集合的收益越低。

若一个次模函数 $f: 2^{[n]} \rightarrow \mathbb{R}$ 满足 $\forall A \subseteq B \subseteq [n]: f(A) \le f(B)$，则称它是 单调的。

例如拟阵的秩函数就是单调的，因为加入一个新的元素，秩可能不变，也可能增加 $1$。

对于一个单调的次模函数，提出以下问题：

输入：非负且单调的次模函数 $f: 2^{[n]} \rightarrow \mathbb{R}_{\ge 0}$（隐式给出，即给定一个集合可以求值，而无法枚举所有集合），整数 $k \in [n]$

输出：$S \subseteq [n]$ 满足 $|S| = k$ 且最大化 $f(S)$。

还是贪心法，只是把权值从集合大小换成了次模函数：

$$\begin{aligned} &\textbf{function}\space \text{SubmodularMaximization(} \mathbb{U}, f, k\text{)} \\ &\qquad F \leftarrow \emptyset \\ &\qquad \textbf{for} \space t \leftarrow 1 \space \textbf{to} \space k \space \textbf{do} \\ &\qquad \qquad \text{find } i \text{ which maximize } f(F \cup \{i\}) \\ &\qquad \qquad F \leftarrow F \cup \{i\} \\ &\qquad \textbf{return}\space F \end{aligned}$$

显然拟阵不能描述这个问题，而贪心法确实无法给出这个问题的最优解，因为这是一般化的 最大覆盖问题。

定理 2.4.1：$\text{SubmodularMaximization(} \mathbb{U}, f, k\text{)}$ 是一个 $\left(1 – \dfrac{1}{e}\right)$ 倍近似的算法。