定义
在电子转账还未普及的年代，从付款人开出支票到钱从付款人账户里扣走之间是有一段等待的时间的，这段时间被称为浮账期（float time，网上似乎没有找到特别靠谱的翻译）。因为在浮账期这些付出去的钱还是能够产生利息的，人们自然希望这个浮账期越长越好。于是人们就抽象出了这么一个浮账最大化的问题。
输入：带权二分图 \(G=(V,E)\)，其中 \(V=B\cup P\)，一侧是所有银行的集合 \(B\)，另一侧是所有交易的集合 \(P\)，第 \(i\) 个银行到第 \(j\) 个交易的边权为 \(v_{ij}\)，表示第 \(i\) 个银行处理这笔交易所需的浮账时间。整数 \(k\)。
目标：选择 \(k\) 家银行的集合 \(S\subseteq B\)，使得 \[ v(S) = \sum_{j\in P} \max_{i\in S}\{v_{ij}\} \] 最大。
贪心算法
我们很容易想到如下的贪心算法：
- 一开始 \(S=\emptyset\)。
- 然后进行 \(k\) 次循环，每次循环寻找能使目标函数增幅最大的银行 \(i\) 加入 \(S\)。
简单，粗暴，好理解。
分析
引理 1：令 \(S\) 是第 \(h\) 次循环开始时我们的银行集合，第 \(h\) 次循环我们所选的新银行是 \(i_h\)，那么有 \[ v(S\cup \{i_h\}) - v(S)\ge \frac{v(\mathrm{OPT})-v(S)}{k} \] 即反映了一种 “优于平均” 的思想。（感觉类似的引理在贪心算法的分析当中经常会碰到）
要证明这个引理，我们需要引入第二个引理，或者说发掘 \(v(\cdot)\) 的一个重要性质：
引理 2（次模性）：对于任何 \(X\subseteq Y\subset B\) 以及 \(l\in B\setminus Y\)，都有： \[ v(X\cup \{l\}) - v(X) \ge v(Y\cup \{l\}) - v(Y) \] 直观理解：随着集合变大，加入新元素的边际效应递减。
证明：
考虑对于固定的交易 \(j\)，\(j\) 在 \(v(X)\) 当中的贡献是 \(\max_{i\in X}\{v_{ij}\}\)，在 \(v(Y)\) 当中的贡献是 \(\max_{i\in Y}\{v_{ij}\}\)，而因为 \(X\subseteq Y\)，显然有 \[ \max_{i\in X}\{v_{ij}\} \le \max_{i\in Y}\{v_{ij}\} \] 将 \(l\) 加入集合之后，\(v_{lj}\) 加入了比较，有三种情况：
- \(v_{lj} \le \max_{i\in X}\{v_{ij}\}\)，那么 \(X\) 还是 \(Y\) 都不会增加。
- \(\max_{i\in X}\{v_{ij}\} < v_{lj} \le \max_{i\in Y}\{v_{ij}\}\)，那么 \(X\) 这边增加了，而 \(Y\) 这边不增加。
- \(v_{lj} > \max_{i\in Y}\{v_{ij}\}\)，两边的最大值都增加了，但是增加幅度 \(X\) 这边要大于 \(Y\)。
由此可见，对于一个固定的交易 \(j\)，新银行 \(l\) 加入后，\(X\) 这一侧的增加量一定不少于 \(Y\) 这一侧的增加量。因此对于所有交易求和之后，必有 \[ v(X\cup \{l\}) - v(X) \ge v(Y\cup \{l\}) - v(Y) \] 得证。
这个 “边际效应递减” 的性质有一个高端的名字：次模性（Submodularity）。
引理 1 的证明：令 \(\mathrm{OPT}\setminus S = \{i_1,i_2,\cdots,i_p\}\)。注意到显然有 \(p\le |\mathrm{OPT}|=k\)。 \[ \begin{aligned} v(\mathrm{OPT}) &\le v(\mathrm{OPT} \cup S) \\ &= v(S) + v(\mathrm{OPT} \cup S) - v(S) \\ &= v(S) + \sum_{j=1}^p \left(v\left(S\cup \{i_1,i_2,\cdots,i_j\}\right) - v\left(S\cup \{i_1,i_2,\cdots,i_{j-1}\}\right)\right) \end{aligned} \] 那个求和式是一个非常精巧的叠缩。接下来我们运用引理 2，令 \(X=S,Y=S\cup \{i_1,i_2,\cdots,i_{j-1}\}\)： \[ \begin{aligned} v(\mathrm{OPT}) &\le v(S) + \sum_{j=1}^p \left(v\left(S\cup \{i_1,i_2,\cdots,i_j\}\right) - v\left(S\cup \{i_1,i_2,\cdots,i_{j-1}\}\right)\right) \\ &\le v(S) + \sum_{j=1}^p (v(S\cup\{i_j\}) - v(S)) \\ &\le v(S) + \sum_{j=1}^p (v(S\cup\{i_h\}) - v(S)) \\ &= v(S) + p(v(S\cup\{i_h\}) - v(S)) \\ &\le v(S) + k(v(S\cup\{i_h\}) - v(S)) \end{aligned} \] 倒数第三步运用到了我们算法的贪心性质，即 \(v(S\cup\{i_h\}) - v(S) \ge v(S\cup\{i_j\}) - v(S), \forall j\)。接下来我们马上就可以得到引理： \[ \begin{aligned} v(\mathrm{OPT}) &\le v(S) + k(v(S\cup\{i_h\}) - v(S)) \\ v(\mathrm{OPT}) - v(S) &\le k(v(S\cup\{i_h\}) - v(S)) \\ v(S\cup\{i_h\}) - v(S) &\ge \frac{v(\mathrm{OPT}) - v(S)}{k} \end{aligned} \] 证毕。
接下来我们可以开始证明我们算法的近似比了：
定理：我们的算法是一个 \(\left(1 - \frac{1}{e}\right)\) 倍近似算法。
证明：令 \(S_t\) 表示第 \(t\) 次循环后我们所选的银行集合。
由引理可得 \[ v(S_k) - v(S_{k-1}) \ge \frac{v(\mathrm{OPT}) - v(S_{k-1})}{k} \Rightarrow v(S_k) \ge \frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right)v(S_{k-1}) \] 因此 \[ \begin{aligned} v(S_k) &\ge \frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right)v(S_{k-1}) \\ &\ge \frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right) \left(\frac{v(\mathrm{OPT})}{k} + \left(1-\frac{1}{k}\right)v(S_{k-2})\right)\\ &\cdots \\ &\ge \frac{v(\mathrm{OPT})}{k}\left(1+\left(1-\frac{1}{k}\right)+\cdots+\left(1-\frac{1}{k}\right)^{k-1}\right) + \left(1-\frac{1}{k}\right)^kv(S_0) \\ &= \frac{v(\mathrm{OPT})}{k}\left(1+\left(1-\frac{1}{k}\right)+\cdots+\left(1-\frac{1}{k}\right)^{k-1}\right) \\ &= \frac{v(\mathrm{OPT})}{k}\frac{1-\left(1-\frac{1}{k}\right)^k}{1/k} \\ &= v(\mathrm{OPT})\left(1-\left(1-\frac{1}{k}\right)^k \right) \\ &\le \left(1-\left(e^{-\frac{1}{k}}\right)^k \right) v(\mathrm{OPT}) \\ &= \left(1 - \frac{1}{e}\right)v(\mathrm{OPT}) \end{aligned} \] 证毕。
其实分析我们的贪心算法，我们发现我们其实只利用了 \(v(\cdot)\) 的次模性，而没有利用 \(v(\cdot)\) 的具体形式或者题目的具体要求。而次模性足以证明引理 1，引理 1 足以证明近似比。也就是说，我们这个贪心算法及其分析是可以被推广到其他的次模优化问题上的。因此，这个看起来很简单粗暴的贪心算法，其实真的是非常有意思！