在线二分图匹配

在线二分图匹配(Online Bipartite Matching)

传统的二分图最大匹配问题是：给定二分图$G=(A\cup B,E)$（二分图意味着$A$中的点两两没有边相连，$B$中的点两两没有边相连），我们想要找到一个最大的$E$的子集$M$使得$M$中的任意两条边都没有公共端点。传统二分图最大匹配问题可以转化为网络最大流问题，这本质上是因为二分图匹配可以写作线性规划。

现在考虑一个二分图最大匹配问题的在线版本：刚开始我们不知道$G$的全貌，只找到左侧点集$A$，不知道关于$B$和$E$的任何信息。接下来，$B$中的点一个一个到来。一个点$b$到来时会相应给出这个点与$A$中所有相连的边$(a_i,b)$。我们需要在每个点到来时就做出决策：是否选择$(a_i,b)$中的某条边加入匹配。一旦加入匹配就不能反悔。

贪心算法

显然，我们可以构造这样一个确定性的贪心方案：每当$B$中一个点到来时，选择从上往下第一条能够匹配的边加入匹配。可以发现，这样匹配得到的结果一定是一个极大匹配，因为在这个匹配的基础上一定不可能还存在一条边使得它的两个端点都还没有被加入匹配（如果存在，不妨设为$(a_i,b_j)$，那么说明$b_j$在到来时是会加入匹配的但没有选择$a_i$，这说明$b_j$一定已经被匹配，矛盾）。图的一个点覆盖是指一个点集，使得每条边至少有一个端点在这个点集里。这说明，贪心方案的匹配$M$的顶点集合构成了一个大小为$2M$的点覆盖。我们注意到，任何一个点覆盖都至少需要大小为$M$，因为要能让每条边都至少要有一个端点在集合中，至少要让匹配$M$中的每条边在集合中。假设最大匹配是$M_{opt}$，它一定也是一个极大匹配，其顶点集合也是一个点覆盖，大小至少要为$M$。也即$2M_{opt}\geq M$。这意味着贪心算法至少有竞争比$1/2$。

另一方面，对于确定性算法而言，$1/2$是tight的。考虑$|A|=2,|B|=2$。当$b_1$到来时给出$(a_1,b_1),(a_2,b_1)$。此时如果算法选$(a_1,b_1)$，那么adversary可以给出$b_2$到来时的边是$(a_1,b_2)$；如果算法选$(a_2,b_1)$，那么adversary可以给出$b_2$到来时的边是$(a_2,b_2)$。可见确定性算法始终只能给出最大匹配为$1$，而最大匹配实际上是$2$。

所以，我们证明了存在竞争比为$1/2$的确定性算法，并且这是竞争比最大的确定性算法。

Ranking算法

下面我们要讨论一个在线二分图匹配的著名的随机算法，它的竞争比为$1-\dfrac{1}{e}$。

Fractional Version

考虑二分图匹配的线性规划：$\max \sum\limits_{e\in E}x_e\\s.t. \quad \sum\limits_{v \in N(u)}x_{(u,v)}\leq 1,\forall u\in A\\x_e\geq 0,\forall e\in E$。这里我们没有规定$x_e$取整数，因此只可能放大结果。我们把这个问题称为二分图匹配的fractional version，也即我们可以选取分数条边加入匹配，只需保证每个节点处权重的总和不超过$1$即可。我们将会证明，在线的fractional version二分图匹配问题在竞争比上总能比任何原始的二分图匹配问题的在线的随机算法做得更好。因此这里我们首先将要证明在线的fractional version的竞争比可以达到$1-\dfrac{1}{e}$。

对于fractional的在线二分图匹配，我们可以设计下面的Water Filling Algorithm：设初始时所有左侧节点$a_i$的水位都为$0$。对于每个到来的节点$b_i$，我们假设它拥有单位$1$的水流。设$b_i$与$a_{j_1},\cdots,a_{j_k}$有边相连，$b$会找到$a_{j_p}$中水位最低的那些点，然后均匀向所有这些点灌注水流，直到它们与其它一些点水位相平，然后再让所有最低水位的点一起被均匀灌注水流，直到单位$1$的水流被用完，或者所有被灌注的点的水位都已经达到上限$1$。最终，输出左侧节点的水位之和作为答案。

我们来分析Water Filling Algorithm在fractional version问题下的竞争比。我们考虑二分图匹配的线性规划的的对偶规划，写为$\min \sum\limits_{v\in V}y_v\\s.t. \quad y_u+y_v\geq 1,\forall (u,v)\in E\\y_v\geq 0,\forall v\in V$（原矩阵的第$i$行恰好是节点$i$的所有邻居为$1$，所以转置后第$i$行恰好是第$i$条边的端点为$1$）。我们来看这个对偶规划的含义。如果加上$y_v\leq 1,\forall V$的条件并规定$y_v$只能取整数，那么这正是二分图的最小点覆盖问题。原问题可以看作最小点覆盖问题的fractional version，放松添加的条件只会让结果更大。

现在我们打算在Water Filling Algorithm进行的过程中，维护一个相应的fractional version的最小点覆盖“算法”。我们假定有一个定义在$[0,1]$实数区间上的单调递增函数$g(x)$，这里我们令$g(x)=e^{x-1}$并且暂时不解释原因。每当Water Filling Algorithm在边$(a,b)$上注入一个水流微元$\Delta$时，令最小点覆盖中的$y_a$增加$\Delta \cdot g(w_a)$，其中$w_a$是指点$a$当前的水位，令$y_b$增加$\Delta \cdot (1-g(w_a))$。由此可见，对偶规划的目标函数也相应增加了$\Delta$，增量和原规划完全相同。这意味着当算法结束后，对偶规划也会得到同样大小的结果。然而，对偶规划中自变量的取值可能是不满足约束条件的。下面我们证明，如果把$y_u+y_v\geq 1$这一条件修改为$y_u+y_v\geq 1-\dfrac{1}{e}$，那么刚才的算法就一定满足约束条件。考虑Water Filling Algorithm注入某条边$(a,b)$的整个过程（每条边只会被注入一次）。如果最终是因为$a$到达了上限$1$而停止了注入，那么意味着整个算法结束时应当有$y_a=\displaystyle\int_{0}^{1}g(x)\text{ d}x=1-\dfrac{1}{e}$，因此$y_a+y_b\geq 1-\dfrac{1}{e}$；如果是$b$用完了$1$的水量而停止注入，那么在注入结束后应当有$y_a=\displaystyle\int_{0}^{w_a}g(x)\text{ d}x=e^{w_a-1}-\dfrac{1}{e}$，$y_b\geq 1-g(w_a)$（这是因为$b$始终在给水位低于$w_a$的节点注水，而$g$单调递增，意味着$b$上的单位增量始终不超过$1-g(w_a)$），那么注入结束后就已经有$y_a+y_b\geq e^{w_a-1}-\dfrac{1}{e}+1-e^{w_a-1}=1-\dfrac{1}{e}$。

由此可见，如果我们构造一个线性规划$\min \sum\limits_{v\in V}y_v\\s.t. \quad y_u+y_v\geq 1-\dfrac{1}{e},\forall (u,v)\in E\\y_v\geq 0,\forall v\in V$，它至少能得到一个与Water Filling Algorithm同样大小的结果。那么只需把每个$y$都增大$\dfrac{1}{1-\frac{1}{e}}$倍，我们就能得到$\min \sum\limits_{v\in V}y_v\\s.t. \quad y_u+y_v\geq 1,\forall (u,v)\in E\\y_v\geq 0,\forall v\in V$的一组解。换言之，对偶规划的最优解小于等于Water Filling Algorithm结果的$\dfrac{1}{1-\frac{1}{e}}$倍，而对偶规划大于等于原规划，也即fractional version的二分图匹配。综上所述，Water Filling与OPT的竞争比$\geq 1-\dfrac{1}{e}$。