基于线性规划的图匹配问题在线算法求解示例

字数 6054 2025-12-22 11:46:10

基于线性规划的图匹配问题在线算法求解示例

我将为您讲解一个线性规划在图匹配问题在线算法中的应用示例。这里的“在线”意味着我们需要在未知未来信息的情况下，对陆续到达的匹配请求进行实时决策，并利用线性规划松弛及其对偶理论来设计具有理论性能保证的算法。

问题描述

我们考虑一个在线二分图最大基数匹配问题的经典模型。

图结构：我们有一个二分图 $G = (L, R, E)$，其中顶点集 $L$ 是 左部顶点，顶点集 $R$ 是 右部顶点，$E \subseteq L \times R$ 是边集。
在线输入：右部顶点 $R$ 是预先已知的。左部顶点 $L$ 是以在线（one-by-one）方式依次到达的。当一个新的左部顶点 $u \in L$ 到达时，我们会立刻得知它与哪些右部顶点 $v \in R$ 相邻（即边 $(u,v) \in E$），但不知道未来将到达哪些左部顶点以及它们的邻接关系。
即时决策：当一个左部顶点 $u$ 到达时，算法必须立刻且不可撤销地决定将 $u$ 匹配给它的一个邻居 $v$，或者选择不匹配 $u$（让其保持未匹配状态）。每个右部顶点 $v$ 最多只能被匹配一次。
目标：我们的目标是最大化最终匹配的总大小（即匹配的边的数量）。

为什么需要在线算法？

这个问题模拟了许多实际场景，例如：

在线广告投放：广告位（右部顶点）是已知的，用户（左部顶点）依次到来。每个用户只对一部分广告位感兴趣（邻接关系）。当用户到来时，必须立刻决定是否展示广告及展示哪个广告位，且每个广告位只能展示给一个用户。
在线任务分配：服务器（右部顶点）是已知的，任务（左部顶点）按序到达。每个任务只能被分配给能处理它的服务器，每个服务器同时只能处理一个任务。

核心挑战与策略

挑战在于，过早地将一个右部顶点匹配掉，可能会失去未来与一个“更好”（能匹配到更多顶点）的左部顶点匹配的机会。我们需要一个贪心策略的指导原则，来决定何时、将哪个右部顶点分配给到达的左部顶点。

我们将使用线性规划（LP）及其对偶来为每个右部顶点动态计算一个“价格”，左部顶点到达时，尝试匹配给其邻居中“价格”最低的顶点。这个价格是从线性规划对偶的角度推导出来的，确保算法具有竞争比分析的理论保障（例如，对于二分图最大基数匹配，存在算法能达到 $1 - \frac{1}{e} \approx 0.632$ 的竞争比）。我们将详细讲解这一构造过程。

解题过程循序渐进讲解

步骤1：构建离线线性规划模型及其对偶

虽然我们面临的是在线问题，但分析在线算法性能的理论工具来自于其对应的离线问题的线性规划松弛。

整数规划模型：
对于已知所有顶点 $L$ 和边 $E$ 的离线问题，最大匹配可以建模为整数规划：

\[ \begin{aligned} \text{最大化} \quad & \sum_{e \in E} x_e \\ \text{满足} \quad & \sum_{v \in N(u)} x_{(u,v)} \le 1 \quad \forall u \in L \quad (\text{每个左顶点最多一度}) \\ & \sum_{u \in N(v)} x_{(u,v)} \le 1 \quad \forall v \in R \quad (\text{每个右顶点最多一度}) \\ & x_e \in \{0, 1\} \quad \forall e \in E \end{aligned} \]

其中 $N(\cdot)$ 表示邻居集合，$x_e=1$ 表示边 $e$ 在匹配中。

线性规划松弛：
将整数约束 $x_e \in \{0,1\}$ 松弛为 $x_e \ge 0$，得到线性规划 $(P)$：

\[ \begin{aligned} \text{最大} \quad & \sum_{e \in E} x_e \\ \text{s.t.} \quad & \sum_{v \in N(u)} x_{uv} \le 1 \quad \forall u \in L \quad (1) \\ & \sum_{u \in N(v)} x_{uv} \le 1 \quad \forall v \in R \quad (2) \\ & x_{uv} \ge 0 \quad \forall (u,v) \in E \end{aligned} \]

由于全幺模矩阵的性质，该LP的最优解就是整数解，对应最大匹配。

构造对偶线性规划：
为约束(1)引入对偶变量 $a_u \ge 0$（对应左顶点 $u$），为约束(2)引入对偶变量 $b_v \ge 0$（对应右顶点 $v$）。得到对偶规划 $(D)$：

\[ \begin{aligned} \text{最小} \quad & \sum_{u \in L} a_u + \sum_{v \in R} b_v \\ \text{s.t.} \quad & a_u + b_v \ge 1 \quad \forall (u,v) \in E \quad (3) \\ & a_u \ge 0, \, b_v \ge 0 \quad \forall u \in L, v \in R \end{aligned} \]

根据线性规划对偶理论，任何可行对偶解的目标函数值都是原始问题最优值的一个**上界**。

步骤2：设计在线算法框架与对偶变量的经济解释

在线算法将基于对偶变量 $b_v$ 来动态决策。我们可以将 $b_v$ 理解为右部顶点 $v$ 的“价格”或“占用成本”。算法将遵循以下经济学直觉：

右部顶点初始价格 $b_v = 0$，表示“免费”。
当一个左部顶点 $u$ 到达时，它希望以最低的总成本 $a_u + b_v$ 满足约束 $a_u + b_v \ge 1$（式(3)）。由于 $a_u$ 是其“效用”，算法会尝试将 $u$ 匹配给其邻居中 $b_v$ 最小的右顶点，并通过匹配操作来支付成本。
匹配操作会增加被匹配的右顶点 $v$ 的价格 $b_v$，这样未来到达的左顶点需要支付更高价格才能使用它，从而避免过早占用稀缺资源。

步骤3：具体在线算法（基于对偶提升的贪心算法）

初始化：
- 对所有右部顶点 $v \in R$，设其价格 $b_v \leftarrow 0$。
- 设 $M \leftarrow \emptyset$ 为当前匹配。
在线处理阶段（对每个依次到达的左部顶点 $u$）：
- 步骤A：尝试寻找匹配伙伴。
  - 获取 $u$ 的邻居集合 $N(u) \subseteq R$。
  - 如果 $N(u)$ 为空，则无法匹配 $u$，直接处理下一个顶点。
  - 否则，在 $N(u)$ 中寻找一个未被匹配且当前价格 $b_v$ 最小的右部顶点 $v$。如果价格相同，可任意选择。
  - 如果所有邻居 $v \in N(u)$ 都已被匹配，则无法匹配 $u$。
- 步骤B：决策与更新。
  - 如果找到了这样的 $v$，算法执行匹配：将边 $(u, v)$ 加入匹配 $M$。
  - 关键操作：提高该右顶点 $v$ 的价格。将其价格 $b_v$ 更新为 $b_v + \Delta$，其中 $\Delta$ 是一个参数。为了获得好的竞争比，通常设置 $\Delta = \frac{1}{n}$（$n = |R|$）或采用指数增长策略 $b_v \leftarrow b_v \cdot (1 + \frac{1}{c}) + \frac{1}{c \cdot n}$，其中 $c$ 是常数。为了简化讲解，我们采用一个经典且直观的增量：令 $b_v \leftarrow b_v + \eta$，其中 $\eta$ 是一个固定的小正值（例如 $\eta = 0.1$），这个增量模拟了“提高成本”的思想。在实际理论分析中，$\eta$ 的选取与竞争比证明紧密相关。

步骤4：一个具体的小规模示例

让我们通过一个例子来演示算法过程。

图结构：设 $R = \{r_1, r_2, r_3\}$（已知）。
在线左顶点序列：$l_1, l_2, l_3, l_4$ 依次到达。
邻接关系（按到达顺序揭示）：
- $l_1$ 到达：邻居 $N(l_1) = \{r_1, r_2\}$。
- $l_2$ 到达：邻居 $N(l_2) = \{r_2, r_3\}$。
- $l_3$ 到达：邻居 $N(l_3) = \{r_1\}$。
- $l_4$ 到达：邻居 $N(l_4) = \{r_1, r_3\}$。
算法参数：设价格增量 $\eta = 0.5$。

执行过程：

初始化：$b_{r1}=0, b_{r2}=0, b_{r3}=0$。$M=\emptyset$。
$l_1$ 到达：邻居 $\{r_1, r_2\}$，价格均为0。选择 $r_1$（最小，可任选）。匹配 $(l_1, r_1)$。更新 $b_{r1} = 0 + 0.5 = 0.5$。
- 状态：$M = \{(l_1, r_1)\}$， $b=(0.5, 0, 0)$。
$l_2$ 到达：邻居 $\{r_2, r_3\}$，价格 $b_{r2}=0, b_{r3}=0$。选择 $r_2$。匹配 $(l_2, r_2)$。更新 $b_{r2} = 0 + 0.5 = 0.5$。
- 状态：$M = \{(l_1, r_1), (l_2, r_2)\}$， $b=(0.5, 0.5, 0)$。
$l_3$ 到达：邻居 $\{r_1\}$。但 $r_1$ 已被匹配（$b_{r1}=0.5$），价格高低在此处不影响可行性。由于 $r_1$ 已被占用，$l_3$ 无法匹配。
- 状态：$M$ 不变。
$l_4$ 到达：邻居 $\{r_1, r_3\}$。$r_1$ 已被匹配，考虑 $r_3$，价格 $b_{r3}=0$（未被匹配）。匹配 $(l_4, r_3)$。更新 $b_{r3} = 0 + 0.5 = 0.5$。
- 最终状态：$M = \{(l_1, r_1), (l_2, r_2), (l_4, r_3)\}$， $b=(0.5, 0.5, 0.5)$。

结果：在线算法找到了大小为3的匹配。对于这个简单例子，离线最优匹配也是3（例如 $\{(l_1,r_2), (l_2,r_3), (l_3,r_1)\}$ 或 $\{(l_1,r_2), (l_2,r_3), (l_4,r_1)\}$ 等）。算法达到了最优。

步骤5：竞争比分析与对偶可行性（概念性解释）

在线算法的性能通常用竞争比来衡量：$\text{竞争比} = \inf_{\text{所有输入序列}} \frac{\text{在线算法目标值}}{\text{离线最优目标值}}$。

构造对偶解：
- 对于算法最终得到的匹配 $M$，以及每个右顶点 $v$ 的最终价格 $b_v$。
- 对于每个左顶点 $u$：
  - 如果 $u$ 被匹配（设匹配边为 $(u,v)$），我们设其对应的对偶变量 $a_u = 1 - b_v^{\text{(匹配前)}}$。这里 $b_v^{\text{(匹配前)}}$ 是 $u$ 匹配 $v$ 之前 $v$ 的价格。
  - 如果 $u$ 未被匹配，我们设 $a_u = 0$。
验证对偶可行性：
- 检查是否对所有边 $(u,v) \in E$，都有 $a_u + b_v \ge 1$。
  - 如果 $(u,v)$ 是匹配边：由 $a_u$ 的定义，$a_u + b_v^{\text{(匹配前)}} = 1$。由于匹配后 $b_v$ 只增不减，所以 $a_u + b_v \ge 1$。
  - 如果 $(u,v)$ 不是匹配边：有两种情况。a) $u$ 未被匹配：$a_u=0$，但算法在 $u$ 到达时，之所以没有通过边 $(u,v)$ 匹配，一定是因为当时 $v$ 已经被匹配（价格 $b_v$ 至少为 $\eta$）或者 $v$ 不是其当时的最便宜邻居。在精心设计的增量规则（如指数增长）下，可以证明这仍然能保证 $a_u + b_v \ge 1$。b) $u$ 被匹配给了另一个顶点 $v'$：这通常意味着 $u$ 到达时，$b_{v'} \le b_v$（贪心选择），结合 $a_u$ 的构造，也能推导出约束成立。
计算竞争比：
- 在线算法的匹配大小 $|M| = \sum_{(u,v) \in M} 1$。
- 另一方面，考虑我们构造的对偶解 $(a, b)$ 的目标函数值：
  $\sum_{u} a_u + \sum_{v} b_v$。
- 可以证明，对于每个匹配边 $(u,v)$，有 $a_u + b_v^{\text{(匹配前)}} = 1$，并且最终 $b_v$ 与 $b_v^{\text{(匹配前)}}$ 的关系由更新规则决定。
- 通过代数推导，可以将在线算法的收益 $|M|$ 与对偶目标值联系起来，形如 $|M| \ge \alpha \cdot (\sum_{u} a_u + \sum_{v} b_v)$，其中 $\alpha$ 是一个常数（例如 $1 - \frac{1}{e}$）。
- 根据线性规划弱对偶定理，任何对偶可行解的目标值 $\sum a_u + \sum b_v$ 不小于原始离线最优解的值 $OPT_{LP}$，而 $OPT_{LP}$ 又等于离线整数最优解 $OPT$（对于二分图匹配）。
- 因此，我们得到 $|M| \ge \alpha \cdot OPT$，即竞争比至少为 $\alpha$。

总结：通过将右顶点价格 $b_v$ 作为对偶变量，并设计合理的价格更新规则（如 $b_v \leftarrow b_v \cdot (1 + \frac{1}{k}) + \frac{1}{k \cdot n}$，其中 $k$ 是调优参数），可以证明该类算法能达到 $1 - \frac{1}{e}$ 的竞争比。我们所讲的简化增量版本（$\eta=0.5$）直观地体现了利用对偶价格指导在线贪心决策的核心思想，而理论上的最优参数则需要更精细的分析来保证对偶可行性并最大化竞争比。

这个示例展示了线性规划对偶理论如何为在线决策问题提供强大的算法设计框架和性能分析工具。

基于线性规划的图匹配问题在线算法求解示例我将为您讲解一个线性规划在图匹配问题在线算法中的应用示例。这里的“在线”意味着我们需要在未知未来信息的情况下，对陆续到达的匹配请求进行实时决策，并利用线性规划松弛及其对偶理论来设计具有理论性能保证的算法。问题描述我们考虑一个在线二分图最大基数匹配问题的经典模型。图结构：我们有一个二分图 $G = (L, R, E)$，其中顶点集 $L$ 是左部顶点，顶点集 $R$ 是右部顶点，$E \subseteq L \times R$ 是边集。在线输入：右部顶点 $R$ 是预先已知的。左部顶点 $L$ 是以在线（one-by-one）方式依次到达的。当一个新的左部顶点 $u \in L$ 到达时，我们会立刻得知它与哪些右部顶点 $v \in R$ 相邻（即边 $(u,v) \in E$），但不知道未来将到达哪些左部顶点以及它们的邻接关系。即时决策：当一个左部顶点 $u$ 到达时，算法必须立刻且不可撤销地决定将 $u$ 匹配给它的一个邻居 $v$，或者选择不匹配 $u$（让其保持未匹配状态）。每个右部顶点 $v$ 最多只能被匹配一次。目标：我们的目标是最大化最终匹配的总大小（即匹配的边的数量）。为什么需要在线算法？这个问题模拟了许多实际场景，例如：在线广告投放：广告位（右部顶点）是已知的，用户（左部顶点）依次到来。每个用户只对一部分广告位感兴趣（邻接关系）。当用户到来时，必须立刻决定是否展示广告及展示哪个广告位，且每个广告位只能展示给一个用户。在线任务分配：服务器（右部顶点）是已知的，任务（左部顶点）按序到达。每个任务只能被分配给能处理它的服务器，每个服务器同时只能处理一个任务。核心挑战与策略挑战在于，过早地将一个右部顶点匹配掉，可能会失去未来与一个“更好”（能匹配到更多顶点）的左部顶点匹配的机会。我们需要一个贪心策略的指导原则，来决定何时、将哪个右部顶点分配给到达的左部顶点。我们将使用线性规划（LP）及其对偶来为每个右部顶点动态计算一个“价格”，左部顶点到达时，尝试匹配给其邻居中“价格”最低的顶点。这个价格是从线性规划对偶的角度推导出来的，确保算法具有竞争比分析的理论保障（例如，对于二分图最大基数匹配，存在算法能达到 $1 - \frac{1}{e} \approx 0.632$ 的竞争比）。我们将详细讲解这一构造过程。解题过程循序渐进讲解步骤1：构建离线线性规划模型及其对偶虽然我们面临的是在线问题，但分析在线算法性能的理论工具来自于其对应的离线问题的线性规划松弛。整数规划模型：对于已知所有顶点 $L$ 和边 $E$ 的离线问题，最大匹配可以建模为整数规划： \[ \begin{aligned} \text{最大化} \quad & \sum_ {e \in E} x_ e \\ \text{满足} \quad & \sum_ {v \in N(u)} x_ {(u,v)} \le 1 \quad \forall u \in L \quad (\text{每个左顶点最多一度}) \\ & \sum_ {u \in N(v)} x_ {(u,v)} \le 1 \quad \forall v \in R \quad (\text{每个右顶点最多一度}) \\ & x_ e \in \{0, 1\} \quad \forall e \in E \end{aligned} \] 其中 $N(\cdot)$ 表示邻居集合，$x_ e=1$ 表示边 $e$ 在匹配中。线性规划松弛：将整数约束 $x_ e \in \{0,1\}$ 松弛为 $x_ e \ge 0$，得到线性规划 $(P)$： \[ \begin{aligned} \text{最大} \quad & \sum_ {e \in E} x_ e \\ \text{s.t.} \quad & \sum_ {v \in N(u)} x_ {uv} \le 1 \quad \forall u \in L \quad (1) \\ & \sum_ {u \in N(v)} x_ {uv} \le 1 \quad \forall v \in R \quad (2) \\ & x_ {uv} \ge 0 \quad \forall (u,v) \in E \end{aligned} \] 由于全幺模矩阵的性质，该LP的最优解就是整数解，对应最大匹配。构造对偶线性规划：为约束(1)引入对偶变量 $a_ u \ge 0$（对应左顶点 $u$），为约束(2)引入对偶变量 $b_ v \ge 0$（对应右顶点 $v$）。得到对偶规划 $(D)$： \[ \begin{aligned} \text{最小} \quad & \sum_ {u \in L} a_ u + \sum_ {v \in R} b_ v \\ \text{s.t.} \quad & a_ u + b_ v \ge 1 \quad \forall (u,v) \in E \quad (3) \\ & a_ u \ge 0, \, b_ v \ge 0 \quad \forall u \in L, v \in R \end{aligned} \] 根据线性规划对偶理论，任何可行对偶解的目标函数值都是原始问题最优值的一个上界。步骤2：设计在线算法框架与对偶变量的经济解释在线算法将基于对偶变量 $b_ v$ 来动态决策。我们可以将 $b_ v$ 理解为右部顶点 $v$ 的“价格”或“占用成本”。算法将遵循以下经济学直觉：右部顶点初始价格 $b_ v = 0$，表示“免费”。当一个左部顶点 $u$ 到达时，它希望以最低的总成本 $a_ u + b_ v$ 满足约束 $a_ u + b_ v \ge 1$（式(3)）。由于 $a_ u$ 是其“效用”，算法会尝试将 $u$ 匹配给其邻居中 $b_ v$ 最小的右顶点，并通过匹配操作来支付成本。匹配操作会增加被匹配的右顶点 $v$ 的价格 $b_ v$，这样未来到达的左顶点需要支付更高价格才能使用它，从而避免过早占用稀缺资源。步骤3：具体在线算法（基于对偶提升的贪心算法）初始化：对所有右部顶点 $v \in R$，设其价格 $b_ v \leftarrow 0$。设 $M \leftarrow \emptyset$ 为当前匹配。在线处理阶段（对每个依次到达的左部顶点 $u$）：步骤A：尝试寻找匹配伙伴。获取 $u$ 的邻居集合 $N(u) \subseteq R$。如果 $N(u)$ 为空，则无法匹配 $u$，直接处理下一个顶点。否则，在 $N(u)$ 中寻找一个未被匹配且当前价格 $b_ v$ 最小的右部顶点 $v$。如果价格相同，可任意选择。如果所有邻居 $v \in N(u)$ 都已被匹配，则无法匹配 $u$。步骤B：决策与更新。如果找到了这样的 $v$，算法执行匹配：将边 $(u, v)$ 加入匹配 $M$。关键操作：提高该右顶点 $v$ 的价格。将其价格 $b_ v$ 更新为 $b_ v + \Delta$，其中 $\Delta$ 是一个参数。为了获得好的竞争比，通常设置 $\Delta = \frac{1}{n}$（$n = |R|$）或采用指数增长策略 $b_ v \leftarrow b_ v \cdot (1 + \frac{1}{c}) + \frac{1}{c \cdot n}$，其中 $c$ 是常数。为了简化讲解，我们采用一个经典且直观的增量：令 $b_ v \leftarrow b_ v + \eta$，其中 $\eta$ 是一个固定的小正值（例如 $\eta = 0.1$），这个增量模拟了“提高成本”的思想。在实际理论分析中，$\eta$ 的选取与竞争比证明紧密相关。步骤4：一个具体的小规模示例让我们通过一个例子来演示算法过程。图结构：设 $R = \{r_ 1, r_ 2, r_ 3\}$（已知）。在线左顶点序列：$l_ 1, l_ 2, l_ 3, l_ 4$ 依次到达。邻接关系（按到达顺序揭示）： $l_ 1$ 到达：邻居 $N(l_ 1) = \{r_ 1, r_ 2\}$。 $l_ 2$ 到达：邻居 $N(l_ 2) = \{r_ 2, r_ 3\}$。 $l_ 3$ 到达：邻居 $N(l_ 3) = \{r_ 1\}$。 $l_ 4$ 到达：邻居 $N(l_ 4) = \{r_ 1, r_ 3\}$。算法参数：设价格增量 $\eta = 0.5$。执行过程：初始化：$b_ {r1}=0, b_ {r2}=0, b_ {r3}=0$。$M=\emptyset$。 $l_ 1$ 到达：邻居 $\{r_ 1, r_ 2\}$，价格均为0。选择 $r_ 1$（最小，可任选）。匹配 $(l_ 1, r_ 1)$。更新 $b_ {r1} = 0 + 0.5 = 0.5$。状态：$M = \{(l_ 1, r_ 1)\}$， $b=(0.5, 0, 0)$。 $l_ 2$ 到达：邻居 $\{r_ 2, r_ 3\}$，价格 $b_ {r2}=0, b_ {r3}=0$。选择 $r_ 2$。匹配 $(l_ 2, r_ 2)$。更新 $b_ {r2} = 0 + 0.5 = 0.5$。状态：$M = \{(l_ 1, r_ 1), (l_ 2, r_ 2)\}$， $b=(0.5, 0.5, 0)$。 $l_ 3$ 到达：邻居 $\{r_ 1\}$。但 $r_ 1$ 已被匹配（$b_ {r1}=0.5$），价格高低在此处不影响可行性。由于 $r_ 1$ 已被占用，$l_ 3$ 无法匹配。状态：$M$ 不变。 $l_ 4$ 到达：邻居 $\{r_ 1, r_ 3\}$。$r_ 1$ 已被匹配，考虑 $r_ 3$，价格 $b_ {r3}=0$（未被匹配）。匹配 $(l_ 4, r_ 3)$。更新 $b_ {r3} = 0 + 0.5 = 0.5$。最终状态：$M = \{(l_ 1, r_ 1), (l_ 2, r_ 2), (l_ 4, r_ 3)\}$， $b=(0.5, 0.5, 0.5)$。结果：在线算法找到了大小为3的匹配。对于这个简单例子，离线最优匹配也是3（例如 $\{(l_ 1,r_ 2), (l_ 2,r_ 3), (l_ 3,r_ 1)\}$ 或 $\{(l_ 1,r_ 2), (l_ 2,r_ 3), (l_ 4,r_ 1)\}$ 等）。算法达到了最优。步骤5：竞争比分析与对偶可行性（概念性解释）在线算法的性能通常用竞争比来衡量：$\text{竞争比} = \inf_ {\text{所有输入序列}} \frac{\text{在线算法目标值}}{\text{离线最优目标值}}$。构造对偶解：对于算法最终得到的匹配 $M$，以及每个右顶点 $v$ 的最终价格 $b_ v$。对于每个左顶点 $u$：如果 $u$ 被匹配（设匹配边为 $(u,v)$），我们设其对应的对偶变量 $a_ u = 1 - b_ v^{\text{(匹配前)}}$。这里 $b_ v^{\text{(匹配前)}}$ 是 $u$ 匹配 $v$ 之前 $v$ 的价格。如果 $u$ 未被匹配，我们设 $a_ u = 0$。验证对偶可行性：检查是否对所有边 $(u,v) \in E$，都有 $a_ u + b_ v \ge 1$。如果 $(u,v)$ 是匹配边：由 $a_ u$ 的定义，$a_ u + b_ v^{\text{(匹配前)}} = 1$。由于匹配后 $b_ v$ 只增不减，所以 $a_ u + b_ v \ge 1$。如果 $(u,v)$ 不是匹配边：有两种情况。a) $u$ 未被匹配：$a_ u=0$，但算法在 $u$ 到达时，之所以没有通过边 $(u,v)$ 匹配，一定是因为当时 $v$ 已经被匹配（价格 $b_ v$ 至少为 $\eta$）或者 $v$ 不是其当时的最便宜邻居。在精心设计的增量规则（如指数增长）下，可以证明这仍然能保证 $a_ u + b_ v \ge 1$。b) $u$ 被匹配给了另一个顶点 $v'$：这通常意味着 $u$ 到达时，$b_ {v'} \le b_ v$（贪心选择），结合 $a_ u$ 的构造，也能推导出约束成立。计算竞争比：在线算法的匹配大小 $|M| = \sum_ {(u,v) \in M} 1$。另一方面，考虑我们构造的对偶解 $(a, b)$ 的目标函数值： $\sum_ {u} a_ u + \sum_ {v} b_ v$。可以证明，对于每个匹配边 $(u,v)$，有 $a_ u + b_ v^{\text{(匹配前)}} = 1$，并且最终 $b_ v$ 与 $b_ v^{\text{(匹配前)}}$ 的关系由更新规则决定。通过代数推导，可以将在线算法的收益 $|M|$ 与对偶目标值联系起来，形如 $|M| \ge \alpha \cdot (\sum_ {u} a_ u + \sum_ {v} b_ v)$，其中 $\alpha$ 是一个常数（例如 $1 - \frac{1}{e}$）。根据线性规划弱对偶定理，任何对偶可行解的目标值 $\sum a_ u + \sum b_ v$ 不小于原始离线最优解的值 $OPT_ {LP}$，而 $OPT_ {LP}$ 又等于离线整数最优解 $OPT$（对于二分图匹配）。因此，我们得到 $|M| \ge \alpha \cdot OPT$，即竞争比至少为 $\alpha$。总结：通过将右顶点价格 $b_ v$ 作为对偶变量，并设计合理的价格更新规则（如 $b_ v \leftarrow b_ v \cdot (1 + \frac{1}{k}) + \frac{1}{k \cdot n}$，其中 $k$ 是调优参数），可以证明该类算法能达到 $1 - \frac{1}{e}$ 的竞争比。我们所讲的简化增量版本（$\eta=0.5$）直观地体现了利用对偶价格指导在线贪心决策的核心思想，而理论上的最优参数则需要更精细的分析来保证对偶可行性并最大化竞争比。这个示例展示了线性规划对偶理论如何为在线决策问题提供强大的算法设计框架和性能分析工具。