PACT 07/04 浮账最大化（次模优化）

Posted on 2020-07-06 Edited on 2022-06-14 Views:

定义

在电子转账还未普及的年代，从付款人开出支票到钱从付款人账户里扣走之间是有一段等待的时间的，这段时间被称为浮账期（float time，网上似乎没有找到特别靠谱的翻译）。因为在浮账期这些付出去的钱还是能够产生利息的，人们自然希望这个浮账期越长越好。于是人们就抽象出了这么一个浮账最大化的问题。

输入：带权二分图 G=(V,E) ，其中 $V=B\cup P$ ，一侧是所有银行的集合，另一侧是所有交易的集合，第个银行到第个交易的边权为 $v_{ij}$ ，表示第个银行处理这笔交易所需的浮账时间。整数。

目标：选择家银行的集合 $S\subseteq B$ ，使得

$v(S) = \sum_{j\in P} \max_{i\in S}\{v_{ij}\}$

最大。

贪心算法

我们很容易想到如下的贪心算法：

一开始 $S=\emptyset$ 。
然后进行次循环，每次循环寻找能使目标函数增幅最大的银行加入。

简单，粗暴，好理解。

分析

引理1：令是第次循环开始时我们的银行集合，第次循环我们所选的新银行是 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)$

直观理解：随着集合变大，加入新元素的边际效应递减。

证明：

考虑对于固定的交易，在 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}\}$

将

加入集合之后， $v_{lj}$ 加入了比较，有三种情况：

$v_{lj} \le \max_{i\in X}\{v_{ij}\}$ ，那么还是都不会增加。
$\max_{i\in X}\{v_{ij}\} < v_{lj} \le \max_{i\in Y}\{v_{ij}\}$ ，那么这边增加了，而这边不增加。
$v_{lj} > \max_{i\in Y}\{v_{ij}\}$ ，两边的最大值都增加了，但是增加幅度这边要大于。

由此可见，对于一个固定的交易，新银行加入后，这一侧的增加量一定不少于这一侧的增加量。因此对于所有交易求和之后，必有

$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 表示第次循环后我们所选的银行集合。

由引理可得

$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足以证明近似比。也就是说，我们这个贪心算法及其分析是可以被推广到其他的次模优化问题上的。因此，这个看起来很简单粗暴的贪心算法，其实真的是非常有意思！