PACT 07/04 浮账最大化(次模优化)
定义
在电子转账还未普及的年代,从付款人开出支票到钱从付款人账户里扣走之间是有一段等待的时间的,这段时间被称为浮账期(float time,网上似乎没有找到特别靠谱的翻译)。因为在浮账期这些付出去的钱还是能够产生利息的,人们自然希望这个浮账期越长越好。于是人们就抽象出了这么一个浮账最大化的问题。
输入:带权二分图,其中
,一侧是所有银行的集合
,另一侧是所有交易的集合
,第
个银行到第
个交易的边权为
,表示第
个银行处理这笔交易所需的浮账时间。整数
。
目标:选择家银行的集合
,使得
贪心算法
我们很容易想到如下的贪心算法:
- 一开始
。
- 然后进行
次循环,每次循环寻找能使目标函数增幅最大的银行
加入
。
简单,粗暴,好理解。
分析
引理1:令是第
次循环开始时我们的银行集合,第
次循环我们所选的新银行是
,那么有
要证明这个引理,我们需要引入第二个引理,或者说发掘的一个重要性质:
引理2(次模性):对于任何以及
,都有:
证明:
考虑对于固定的交易,
在
当中的贡献是
,在
当中的贡献是
,而因为
,显然有
,那么
还是
都不会增加。
,那么
这边增加了,而
这边不增加。
,两边的最大值都增加了,但是增加幅度
这边要大于
。
由此可见,对于一个固定的交易,新银行
加入后,
这一侧的增加量一定不少于
这一侧的增加量。因此对于所有交易求和之后,必有
这个“边际效应递减”的性质有一个高端的名字:次模性(Submodularity)。
引理1的证明:令。注意到显然有
。
接下来我们可以开始证明我们算法的近似比了:
定理:我们的算法是一个倍近似算法。
证明:令表示第
次循环后我们所选的银行集合。
由引理可得
其实分析我们的贪心算法,我们发现我们其实只利用了的次模性,而没有利用
的具体形式或者题目的具体要求。而次模性足以证明引理1,引理1足以证明近似比。也就是说,我们这个贪心算法及其分析是可以被推广到其他的次模优化问题上的。因此,这个看起来很简单粗暴的贪心算法,其实真的是非常有意思!