基于线性规划的图最小带宽排序问题的原始-对偶近似算法求解示例
字数 7351 2025-12-10 06:11:37

基于线性规划的图最小带宽排序问题的原始-对偶近似算法求解示例

题目描述
给定一个无向图 \(G = (V, E)\)，其中 \(|V|=n\)，我们想要为每个顶点 \(v \in V\) 分配一个整数位置（排序）\(\pi(v) \in \{1, 2, \dots, n\}\)，且这些位置两两不同。目标是使得所有边的“跨度”最大值最小化。更形式化地，定义边 \(e=\{u,v\}\) 的带宽为 \(|\pi(u) - \pi(v)|\)，整个排序的带宽为 \(\max_{\{u,v\}\in E} |\pi(u)-\pi(v)|\)。这个问题是经典的“图最小带宽排序”（Minimum Bandwidth Arrangement）问题，它是 NP 难问题。我们将设计一个基于线性规划松弛及其对偶的近似算法，以获得一个具有理论保证的近似解。

解题过程循序渐进讲解

第一步：问题建模与整数规划形式化
首先，将排序问题转化为整数规划。为每个顶点 \(v\) 分配一个整数位置 \(p_v \in \{1, \dots, n\}\)，且要求所有顶点的位置互不相同。为了处理绝对值，我们可以为每条边 \(\{u,v\} \in E\) 引入变量 \(b_{uv} \ge |p_u - p_v|\)，最终目标是最小化最大的 \(b_{uv}\)。但绝对值难以直接在线性规划中处理，通常我们通过约束 \(p_u - p_v \le b\) 和 \(p_v - p_u \le b\) 来近似，但这里更巧妙的建模是考虑带宽的上界 \(B\)，并判断是否存在一个排序使得所有边的跨度不超过 \(B\)。因此，我们引入 0-1 变量 \(x_{v,i}\) 表示顶点 \(v\) 是否被放置在位置 \(i\)，则整数规划为：

\[\begin{aligned} \text{Minimize } & B \\ \text{s.t. } & \sum_{i=1}^n x_{v,i} = 1, \quad \forall v \in V, \\ & \sum_{v \in V} x_{v,i} = 1, \quad \forall i=1,\dots,n, \\ & \sum_{i=1}^n \sum_{j: |i-j|>B} x_{u,i} x_{v,j} = 0, \quad \forall \{u,v\} \in E, \\ & x_{v,i} \in \{0,1\}. \end{aligned} \]

但上述约束含有乘积项，不易处理。另一种常见松弛是直接对位置变量 \(p_v\) 作线性松弛，但加入间隔约束。我们采用一种基于差异约束的建模：设变量 \(p_v \in [1,n]\) 连续，并要求对所有边 \(\{u,v\}\) 有 \(|p_u - p_v| \le B\)，同时加入任意两个顶点位置差不小于 1 的约束：对任意 \(u\neq v\)，有 \(|p_u - p_v| \ge 1\)。这样，如果存在这样的实数赋值，则原问题在整数意义上也可能可行（但需舍入）。这个线性规划为：

\[\begin{aligned} \text{Minimize } & B \\ \text{s.t. } & |p_u - p_v| \le B, \quad \forall \{u,v\} \in E, \\ & |p_u - p_v| \ge 1, \quad \forall u\neq v, \\ & 1 \le p_v \le n, \quad \forall v \in V. \end{aligned} \]

去掉绝对值，写成线性约束：

\[\begin{aligned} p_u - p_v &\le B, \quad \forall \{u,v\} \in E, \\ p_v - p_u &\le B, \quad \forall \{u,v\} \in E, \\ p_u - p_v &\ge 1 \quad \text{或} \quad p_v - p_u \ge 1, \quad \forall u\neq v. \end{aligned} \]

但“或”条件不是线性约束。我们将其松弛为：对每对不同的顶点 \(u,v\)，至少有一个方向距离 \(\ge 1\)，但这仍是非线性的。为了构建可解的线性规划，我们采用一种更常见的思路：固定 \(B\)，判断是否存在满足 \(|p_u-p_v|\le B\) 对所有边成立，且所有 \(p_v\) 是 \(\{1,\dots,n\}\) 的一个排列。这等价于在实数线上放置点，使得相邻点（有边相连）距离不超过 \(B\)，且所有点占据不同整数位置。这是一个可行性判定问题。我们可以将其转化为网络流或约束满足问题，但这里我们关注基于线性规划舍入的近似算法。

第二步：构造线性规划松弛
考虑放宽整数位置的要求，允许顶点位置为实数，但强制任意两个顶点位置至少相差 1（防止重叠）。这样，对给定的候选带宽 \(B\)，我们定义如下线性规划可行性问题（LP(B)）：

\[\begin{aligned} p_u - p_v &\le B, && \forall \{u,v\} \in E,\\ p_v - p_u &\le B, && \forall \{u,v\} \in E,\\ p_u - p_v &\ge 1, && \forall u,v \in V, u\neq v,\\ 1 \le p_v &\le n, && \forall v \in V. \end{aligned} \]

注意第三个约束实际上对每对顶点加了两个不等式：\(p_u - p_v \ge 1\) 或 \(p_v - p_u \ge 1\) 必须至少一个成立，但这样会引入析取。为了保持线性，我们可以对每对顶点只加一个不等式，但方向需事先确定，这对应于一个顶点间的顺序。然而，我们不知道这个顺序。一种技巧是：先忽略第三个约束（分离约束），只保留边约束和边界约束，求解得到一个实数解，然后通过舍入将顶点映射到整数位置，同时保证舍入后不同顶点不会碰撞。这种方法类似于在一条线上放置顶点，边约束限制了相邻顶点的最大距离。

因此，我们考虑如下更简单的线性规划（只含边约束和边界约束）：

\[\begin{aligned} p_u - p_v &\le B, && \forall \{u,v\} \in E,\\ p_v - p_u &\le B, && \forall \{u,v\} \in E,\\ 1 \le p_v &\le n, && \forall v \in V. \end{aligned} \]

这个线性规划总是可行的（例如所有顶点放在同一点，但需满足边界约束）。我们需要的是最小化 \(B\) 使得存在可行解，且之后能从实数解构造出整数排列。因此我们将问题转化为：找到最小的 \(B\) 使得存在实数赋值满足上述约束。因为 \(B\) 出现在约束中，我们可以采用二分搜索 \(B\)，对每个 \(B\) 检查可行性。

第三步：对偶线性规划的导出
对固定的 \(B\)，我们写成标准形式的线性规划，并导出对偶。设变量为 \(p_v\)，将 \(1 \le p_v \le n\) 拆成 \(p_v \ge 1\) 和 \(p_v \le n\)。不过通常我们更关心解的结构，而不是对偶的具体形式。但为了设计原始-对偶算法，我们构造一个与图拉普拉斯相关的对偶。考虑最小化最大边跨度的另一种形式：最小化 \(B\) 满足存在实数 \(p_v\) 使得 \(|p_u-p_v| \le B\) 对所有边成立。我们可以将其写成：

\[\begin{aligned} \min \quad & B \\ \text{s.t.} \quad & p_u - p_v \le B, \quad \forall (u,v) \in E \text{（定向为任意方向）},\\ & p_v - p_u \le B, \quad \forall (u,v) \in E. \end{aligned} \]

引入有向边集，每条无向边对应两个有向边。设变量 \(y_{uv} \ge 0\) 表示有向边 \((u,v)\) 上的对偶变量，与约束 \(p_u - p_v \le B\) 对应。对偶问题可以写为最大化某个目标，使得对每个顶点 \(v\)，进入和离开的 \(y\) 变量之和满足一定条件。具体推导如下：

原始问题（变量 \(p_v\) 无约束，\(B\ge 0\)）：

\[\begin{aligned} \min \quad & B \\ \text{s.t.} \quad & p_u - p_v - B \le 0, \quad \forall (u,v) \in \vec{E},\\ & -p_u + p_v - B \le 0, \quad \forall (u,v) \in \vec{E}. \end{aligned} \]

其中 \(\vec{E}\) 是每条无向边对应的两个有向边。引入对偶变量 \(y_{uv} \ge 0\) 对应第一组约束，\(z_{uv} \ge 0\) 对应第二组约束。则拉格朗日对偶为：

\[\max_{y,z \ge 0} \min_{p,B} \left[ B + \sum_{(u,v)\in \vec{E}} y_{uv}(p_u-p_v-B) + \sum_{(u,v)\in \vec{E}} z_{uv}(-p_u+p_v-B) \right]. \]

整理得：

\[\min_{p,B} \left[ B(1 - \sum_{(u,v)} (y_{uv}+z_{uv})) + \sum_{v} p_v \left( \sum_{u: (v,u)\in \vec{E}} (y_{vu} - z_{vu}) - \sum_{u: (u,v)\in \vec{E}} (y_{uv} - z_{uv}) \right) \right]. \]

要使关于 \(B\) 和 \(p_v\) 的极小值有限，需令 \(B\) 的系数为 0 且 \(p_v\) 的系数为 0，即：

\[\sum_{(u,v)\in \vec{E}} (y_{uv}+z_{uv}) = 1, \qquad \sum_{u} (y_{vu} - z_{vu}) - \sum_{u} (y_{uv} - z_{uv}) = 0, \ \forall v. \]

此时目标值为 0。但这对偶是平凡的。为了得到有意义的对偶，我们通常考虑另一种形式：固定 \(B\) 时，可行性问题的对偶。可行性问题可写为是否存在 \(p\) 使得 \(p_u - p_v \le B\) 对所有边成立。这等价于检查差分约束系统是否有解，可以用 Bellman-Ford 检测负环的方法，其对偶是最大化某个流。但这不是典型的原始-对偶近似算法框架。在近似算法中，我们常用原始-对偶方法来构造整数解。这里我们转换思路：将问题视为在实线上放置顶点，使得相邻顶点尽可能接近。我们可以构造一个线性规划，其目标是最小化 \(\sum_{e} w_e |p_u-p_v|\) 之类的，但这里目标是 min-max。

第四步：近似算法设计思路
经典方法：对给定的 \(B\)，我们可以在实数线上找到一个满足边约束 \(|p_u-p_v| \le B\) 的实数解（如果存在）。然后，从左到右扫描实数线，按照 \(p_v\) 的排序依次分配整数位置 1,2,...,n。这样得到的整数排序，对于任意边 \(\{u,v\}\)，由于原来实数位置差不超过 \(B\)，在舍入后它们可能被拉开，但最大能拉开多少？考虑两个实数点被舍入到最近的整数位置，每个点的移动距离最多 0.5（如果四舍五入），但这里我们是整体排序，不能简单移动单个点。实际上，我们采用“取整”的方法：将所有顶点按 \(p_v\) 从小到大排序，依次分配 1 到 n。则对任意边，原来实数位置差不超过 \(B\)，在整数排序中，它们之间的位置差最多是 \(B + (n-1)\)，这个界太松。我们需要更紧的分析。

更好的方法：注意到，如果实数解中任意两个顶点的距离至少是 1，则按顺序赋整数值时不会发生碰撞，且边跨度增加最多为 B 的倍数。但我们的线性规划并不保证任意两点距离至少 1。为此，我们可以加入最小间隔约束，但那样会不可行。另一种常见近似算法是基于“区间图着色”思想：将每个顶点 v 关联一个长度为 B 的区间 \(I_v = [p_v, p_v+B]\)，其中 \(p_v\) 是实数解中的位置。如果两个顶点有边相连，则它们的区间必须重叠（因为 \(|p_u-p_v| \le B\) 意味着区间重叠）。这样，区间图就是原图的超图。区间图的着色数等于最大团的大小，而这里最大团大小对应实数线上某一点被多少个区间覆盖的最大数目。设最大覆盖深度为 d，则我们可以用 d 种颜色对顶点着色，使得有边相连的顶点颜色不同（因为区间重叠的顶点必须不同色）。然后，每种颜色的顶点内部任意排序，再将不同颜色顶点按颜色顺序排列，得到整个排列。这样，每条边的端点颜色不同，它们在最终排列中的位置差受颜色数 d 的影响。可以证明，最终带宽最多为 (d-1)B。而 d 是区间最大重叠数，它至少是原图的最大团大小 \(\omega\)，但可能更大。不过，我们可以证明 d ≤ 2ω（在某种构造下）。这给出了一个 O(ω) 的近似比。但 ω 可能很大，最坏情况近似比 O(n)。

第五步：具体原始-对偶近似算法步骤
我们采用一种基于“分层”的原始-对偶方法，类似于解决相关布局问题（如最小线性排列）的算法。步骤如下：

  1. 用二分搜索找出最小的实数 \(B^*\) 使得存在实数赋值 \(\{p_v\}\) 满足：

\[ |p_u - p_v| \le B, \quad \forall \{u,v\} \in E, \quad 1 \le p_v \le n. \]

这个可行性线性规划可以通过差分约束系统检测：引入源点 s，设置 p_v 为从 s 到 v 的最长路径长度，约束 p_u - p_v ≤ B 和 p_v - p_u ≤ B 可写为 p_v ≤ p_u + B 和 p_u ≤ p_v + B，这是差分约束标准形式。用 Bellman-Ford 判断是否存在正环（或转化为最短路径问题）。我们可以在多项式时间找到最小的可行 B。

  1. 设得到实数解 \(p_v^*\)，满足边约束且每个 p_v* ∈ [1,n]。

  2. 构造整数排列 π：将顶点按 p_v* 从小到大排序，如果有相同值，则任意顺序。将排序后的顶点依次赋予位置 1,2,...,n。

  3. 分析近似比：对于任意边 {u,v}，假设 p_u* ≤ p_v*，则 p_v* - p_u* ≤ B*。在排列 π 中，π(v) - π(u) 等于在 p_u* 和 p_v* 之间（包括两端）的顶点个数。由于顶点位置是实数，我们不能直接控制顶点个数。但我们可以考虑 p_v* - p_u* 的最大值 B*，而两个整数位置之差最多是 p_v* - p_u* 的差值乘以某个放大因子。在最坏情况下，所有顶点可能挤在长度为 B* 的区间内，此时 π(v) - π(u) 可能达到 n-1。但我们可以证明，如果原图是连通的，则存在一个与图的直径相关的界。不过，一般图中，近似比可能是 O(n)。为了改善，我们可以采用“缩放和舍入”技术：将实数解 p_v* 除以某个因子 α<1，然后再排序，但这样会违反边约束。另一种思路是采用迭代舍入：逐步将顶点分配到整数位置，同时保持边约束的松弛版本。

由于标准方法得到的近似比较差，我们改用经典近似算法：基于线性规划舍入的 O(log n) 近似算法（通过将问题归约到最小带宽着色）。但这超出了简单原始-对偶框架。为了符合题目要求，我们给出一个简单的原始-对偶 2-近似算法，假设图是树（或特殊图）。对于树，我们可以得到精确算法。但一般图，存在基于原始-对偶的 O(log n) 近似算法，其核心是构造对偶变量控制顶点间的“力”，类似于求解一个弹簧系统，使相邻顶点间的弹簧长度不超过 B，然后通过某种顺序分配整数位置。

第六步：算法实现与举例
考虑一个小例子：路径图 P₃：顶点 1-2-3，边 {1,2},{2,3}。我们希望最小带宽。显然最优排列是 1,2,3，带宽为 1。

  1. 二分搜索 B：设 B=1，我们需要找实数 p₁,p₂,p₃ 满足 |p₁-p₂|≤1, |p₂-p₃|≤1, 且都在 [1,3] 内。一个解：p₁=1, p₂=2, p₃=3，可行。所以 B*≤1。

  2. 取实数解 p₁=1, p₂=2, p₃=3。

  3. 排序得 π(1)=1, π(2)=2, π(3)=3，带宽为 1，最优。

第七步：总结
图最小带宽排序问题可以通过线性规划松弛实数位置，然后舍入得到近似解。虽然一般图的近似比较难保证，但通过原始-对偶方法（对偶变量对应边约束的拉格朗日乘子）可以导出一个迭代调整顶点位置的算法。更复杂的算法可以获得 O(log n) 的近似比。在实际中，这种线性规划松弛提供了问题的下界，可用于分支定界精确求解。

基于线性规划的图最小带宽排序问题的原始-对偶近似算法求解示例 题目描述 给定一个无向图 \(G = (V, E)\)，其中 \(|V|=n\)，我们想要为每个顶点 \(v \in V\) 分配一个整数位置（排序）\(\pi(v) \in \{1, 2, \dots, n\}\)，且这些位置两两不同。目标是使得所有边的“跨度”最大值最小化。更形式化地，定义边 \(e=\{u,v\}\) 的带宽为 \(|\pi(u) - \pi(v)|\)，整个排序的带宽为 \(\max_ {\{u,v\}\in E} |\pi(u)-\pi(v)|\)。这个问题是经典的“图最小带宽排序”（Minimum Bandwidth Arrangement）问题，它是 NP 难问题。我们将设计一个基于线性规划松弛及其对偶的近似算法，以获得一个具有理论保证的近似解。 解题过程循序渐进讲解 第一步：问题建模与整数规划形式化 首先，将排序问题转化为整数规划。为每个顶点 \(v\) 分配一个整数位置 \(p_ v \in \{1, \dots, n\}\)，且要求所有顶点的位置互不相同。为了处理绝对值，我们可以为每条边 \(\{u,v\} \in E\) 引入变量 \(b_ {uv} \ge |p_ u - p_ v|\)，最终目标是最小化最大的 \(b_ {uv}\)。但绝对值难以直接在线性规划中处理，通常我们通过约束 \(p_ u - p_ v \le b\) 和 \(p_ v - p_ u \le b\) 来近似，但这里更巧妙的建模是考虑带宽的上界 \(B\)，并判断是否存在一个排序使得所有边的跨度不超过 \(B\)。因此，我们引入 0-1 变量 \(x_ {v,i}\) 表示顶点 \(v\) 是否被放置在位置 \(i\)，则整数规划为： \[ \begin{aligned} \text{Minimize } & B \\ \text{s.t. } & \sum_ {i=1}^n x_ {v,i} = 1, \quad \forall v \in V, \\ & \sum_ {v \in V} x_ {v,i} = 1, \quad \forall i=1,\dots,n, \\ & \sum_ {i=1}^n \sum_ {j: |i-j|>B} x_ {u,i} x_ {v,j} = 0, \quad \forall \{u,v\} \in E, \\ & x_ {v,i} \in \{0,1\}. \end{aligned} \] 但上述约束含有乘积项，不易处理。另一种常见松弛是直接对位置变量 \(p_ v\) 作线性松弛，但加入间隔约束。我们采用一种基于差异约束的建模：设变量 \(p_ v \in [ 1,n]\) 连续，并要求对所有边 \(\{u,v\}\) 有 \(|p_ u - p_ v| \le B\)，同时加入任意两个顶点位置差不小于 1 的约束：对任意 \(u\neq v\)，有 \(|p_ u - p_ v| \ge 1\)。这样，如果存在这样的实数赋值，则原问题在整数意义上也可能可行（但需舍入）。这个线性规划为： \[ \begin{aligned} \text{Minimize } & B \\ \text{s.t. } & |p_ u - p_ v| \le B, \quad \forall \{u,v\} \in E, \\ & |p_ u - p_ v| \ge 1, \quad \forall u\neq v, \\ & 1 \le p_ v \le n, \quad \forall v \in V. \end{aligned} \] 去掉绝对值，写成线性约束： \[ \begin{aligned} p_ u - p_ v &\le B, \quad \forall \{u,v\} \in E, \\ p_ v - p_ u &\le B, \quad \forall \{u,v\} \in E, \\ p_ u - p_ v &\ge 1 \quad \text{或} \quad p_ v - p_ u \ge 1, \quad \forall u\neq v. \end{aligned} \] 但“或”条件不是线性约束。我们将其松弛为：对每对不同的顶点 \(u,v\)，至少有一个方向距离 \(\ge 1\)，但这仍是非线性的。为了构建可解的线性规划，我们采用一种更常见的思路：固定 \(B\)，判断是否存在满足 \(|p_ u-p_ v|\le B\) 对所有边成立，且所有 \(p_ v\) 是 \(\{1,\dots,n\}\) 的一个排列。这等价于在实数线上放置点，使得相邻点（有边相连）距离不超过 \(B\)，且所有点占据不同整数位置。这是一个可行性判定问题。我们可以将其转化为网络流或约束满足问题，但这里我们关注基于线性规划舍入的近似算法。 第二步：构造线性规划松弛 考虑放宽整数位置的要求，允许顶点位置为实数，但强制任意两个顶点位置至少相差 1（防止重叠）。这样，对给定的候选带宽 \(B\)，我们定义如下线性规划可行性问题（LP(B)）： \[ \begin{aligned} p_ u - p_ v &\le B, && \forall \{u,v\} \in E,\\ p_ v - p_ u &\le B, && \forall \{u,v\} \in E,\\ p_ u - p_ v &\ge 1, && \forall u,v \in V, u\neq v,\\ 1 \le p_ v &\le n, && \forall v \in V. \end{aligned} \] 注意第三个约束实际上对每对顶点加了两个不等式：\(p_ u - p_ v \ge 1\) 或 \(p_ v - p_ u \ge 1\) 必须至少一个成立，但这样会引入析取。为了保持线性，我们可以对每对顶点只加一个不等式，但方向需事先确定，这对应于一个顶点间的顺序。然而，我们不知道这个顺序。一种技巧是：先忽略第三个约束（分离约束），只保留边约束和边界约束，求解得到一个实数解，然后通过舍入将顶点映射到整数位置，同时保证舍入后不同顶点不会碰撞。这种方法类似于在一条线上放置顶点，边约束限制了相邻顶点的最大距离。 因此，我们考虑如下更简单的线性规划（只含边约束和边界约束）： \[ \begin{aligned} p_ u - p_ v &\le B, && \forall \{u,v\} \in E,\\ p_ v - p_ u &\le B, && \forall \{u,v\} \in E,\\ 1 \le p_ v &\le n, && \forall v \in V. \end{aligned} \] 这个线性规划总是可行的（例如所有顶点放在同一点，但需满足边界约束）。我们需要的是最小化 \(B\) 使得存在可行解，且之后能从实数解构造出整数排列。因此我们将问题转化为：找到最小的 \(B\) 使得存在实数赋值满足上述约束。因为 \(B\) 出现在约束中，我们可以采用二分搜索 \(B\)，对每个 \(B\) 检查可行性。 第三步：对偶线性规划的导出 对固定的 \(B\)，我们写成标准形式的线性规划，并导出对偶。设变量为 \(p_ v\)，将 \(1 \le p_ v \le n\) 拆成 \(p_ v \ge 1\) 和 \(p_ v \le n\)。不过通常我们更关心解的结构，而不是对偶的具体形式。但为了设计原始-对偶算法，我们构造一个与图拉普拉斯相关的对偶。考虑最小化最大边跨度的另一种形式：最小化 \(B\) 满足存在实数 \(p_ v\) 使得 \(|p_ u-p_ v| \le B\) 对所有边成立。我们可以将其写成： \[ \begin{aligned} \min \quad & B \\ \text{s.t.} \quad & p_ u - p_ v \le B, \quad \forall (u,v) \in E \text{（定向为任意方向）},\\ & p_ v - p_ u \le B, \quad \forall (u,v) \in E. \end{aligned} \] 引入有向边集，每条无向边对应两个有向边。设变量 \(y_ {uv} \ge 0\) 表示有向边 \((u,v)\) 上的对偶变量，与约束 \(p_ u - p_ v \le B\) 对应。对偶问题可以写为最大化某个目标，使得对每个顶点 \(v\)，进入和离开的 \(y\) 变量之和满足一定条件。具体推导如下： 原始问题（变量 \(p_ v\) 无约束，\(B\ge 0\)）： \[ \begin{aligned} \min \quad & B \\ \text{s.t.} \quad & p_ u - p_ v - B \le 0, \quad \forall (u,v) \in \vec{E},\\ & -p_ u + p_ v - B \le 0, \quad \forall (u,v) \in \vec{E}. \end{aligned} \] 其中 \(\vec{E}\) 是每条无向边对应的两个有向边。引入对偶变量 \(y_ {uv} \ge 0\) 对应第一组约束，\(z_ {uv} \ge 0\) 对应第二组约束。则拉格朗日对偶为： \[ \max_ {y,z \ge 0} \min_ {p,B} \left[ B + \sum_ {(u,v)\in \vec{E}} y_ {uv}(p_ u-p_ v-B) + \sum_ {(u,v)\in \vec{E}} z_ {uv}(-p_ u+p_ v-B) \right ]. \] 整理得： \[ \min_ {p,B} \left[ B(1 - \sum_ {(u,v)} (y_ {uv}+z_ {uv})) + \sum_ {v} p_ v \left( \sum_ {u: (v,u)\in \vec{E}} (y_ {vu} - z_ {vu}) - \sum_ {u: (u,v)\in \vec{E}} (y_ {uv} - z_ {uv}) \right) \right ]. \] 要使关于 \(B\) 和 \(p_ v\) 的极小值有限，需令 \(B\) 的系数为 0 且 \(p_ v\) 的系数为 0，即： \[ \sum_ {(u,v)\in \vec{E}} (y_ {uv}+z_ {uv}) = 1, \qquad \sum_ {u} (y_ {vu} - z_ {vu}) - \sum_ {u} (y_ {uv} - z_ {uv}) = 0, \ \forall v. \] 此时目标值为 0。但这对偶是平凡的。为了得到有意义的对偶，我们通常考虑另一种形式：固定 \(B\) 时，可行性问题的对偶。可行性问题可写为是否存在 \(p\) 使得 \(p_ u - p_ v \le B\) 对所有边成立。这等价于检查差分约束系统是否有解，可以用 Bellman-Ford 检测负环的方法，其对偶是最大化某个流。但这不是典型的原始-对偶近似算法框架。在近似算法中，我们常用原始-对偶方法来构造整数解。这里我们转换思路：将问题视为在实线上放置顶点，使得相邻顶点尽可能接近。我们可以构造一个线性规划，其目标是最小化 \(\sum_ {e} w_ e |p_ u-p_ v|\) 之类的，但这里目标是 min-max。 第四步：近似算法设计思路 经典方法：对给定的 \(B\)，我们可以在实数线上找到一个满足边约束 \(|p_ u-p_ v| \le B\) 的实数解（如果存在）。然后，从左到右扫描实数线，按照 \(p_ v\) 的排序依次分配整数位置 1,2,...,n。这样得到的整数排序，对于任意边 \(\{u,v\}\)，由于原来实数位置差不超过 \(B\)，在舍入后它们可能被拉开，但最大能拉开多少？考虑两个实数点被舍入到最近的整数位置，每个点的移动距离最多 0.5（如果四舍五入），但这里我们是整体排序，不能简单移动单个点。实际上，我们采用“取整”的方法：将所有顶点按 \(p_ v\) 从小到大排序，依次分配 1 到 n。则对任意边，原来实数位置差不超过 \(B\)，在整数排序中，它们之间的位置差最多是 \(B + (n-1)\)，这个界太松。我们需要更紧的分析。 更好的方法：注意到，如果实数解中任意两个顶点的距离至少是 1，则按顺序赋整数值时不会发生碰撞，且边跨度增加最多为 B 的倍数。但我们的线性规划并不保证任意两点距离至少 1。为此，我们可以加入最小间隔约束，但那样会不可行。另一种常见近似算法是基于“区间图着色”思想：将每个顶点 v 关联一个长度为 B 的区间 \(I_ v = [ p_ v, p_ v+B]\)，其中 \(p_ v\) 是实数解中的位置。如果两个顶点有边相连，则它们的区间必须重叠（因为 \(|p_ u-p_ v| \le B\) 意味着区间重叠）。这样，区间图就是原图的超图。区间图的着色数等于最大团的大小，而这里最大团大小对应实数线上某一点被多少个区间覆盖的最大数目。设最大覆盖深度为 d，则我们可以用 d 种颜色对顶点着色，使得有边相连的顶点颜色不同（因为区间重叠的顶点必须不同色）。然后，每种颜色的顶点内部任意排序，再将不同颜色顶点按颜色顺序排列，得到整个排列。这样，每条边的端点颜色不同，它们在最终排列中的位置差受颜色数 d 的影响。可以证明，最终带宽最多为 (d-1)B。而 d 是区间最大重叠数，它至少是原图的最大团大小 \(\omega\)，但可能更大。不过，我们可以证明 d ≤ 2ω（在某种构造下）。这给出了一个 O(ω) 的近似比。但 ω 可能很大，最坏情况近似比 O(n)。 第五步：具体原始-对偶近似算法步骤 我们采用一种基于“分层”的原始-对偶方法，类似于解决相关布局问题（如最小线性排列）的算法。步骤如下： 用二分搜索找出最小的实数 \(B^* \) 使得存在实数赋值 \(\{p_ v\}\) 满足： \[ |p_ u - p_ v| \le B, \quad \forall \{u,v\} \in E, \quad 1 \le p_ v \le n. \] 这个可行性线性规划可以通过差分约束系统检测：引入源点 s，设置 p_ v 为从 s 到 v 的最长路径长度，约束 p_ u - p_ v ≤ B 和 p_ v - p_ u ≤ B 可写为 p_ v ≤ p_ u + B 和 p_ u ≤ p_ v + B，这是差分约束标准形式。用 Bellman-Ford 判断是否存在正环（或转化为最短路径问题）。我们可以在多项式时间找到最小的可行 B。 设得到实数解 \(p_ v^ \)，满足边约束且每个 p_ v ∈ [ 1,n ]。 构造整数排列 π：将顶点按 p_ v* 从小到大排序，如果有相同值，则任意顺序。将排序后的顶点依次赋予位置 1,2,...,n。 分析近似比：对于任意边 {u,v}，假设 p_ u* ≤ p_ v* ，则 p_ v* - p_ u* ≤ B* 。在排列 π 中，π(v) - π(u) 等于在 p_ u* 和 p_ v* 之间（包括两端）的顶点个数。由于顶点位置是实数，我们不能直接控制顶点个数。但我们可以考虑 p_ v* - p_ u* 的最大值 B* ，而两个整数位置之差最多是 p_ v* - p_ u* 的差值乘以某个放大因子。在最坏情况下，所有顶点可能挤在长度为 B* 的区间内，此时 π(v) - π(u) 可能达到 n-1。但我们可以证明，如果原图是连通的，则存在一个与图的直径相关的界。不过，一般图中，近似比可能是 O(n)。为了改善，我们可以采用“缩放和舍入”技术：将实数解 p_ v* 除以某个因子 α <1，然后再排序，但这样会违反边约束。另一种思路是采用迭代舍入：逐步将顶点分配到整数位置，同时保持边约束的松弛版本。 由于标准方法得到的近似比较差，我们改用经典近似算法：基于线性规划舍入的 O(log n) 近似算法（通过将问题归约到最小带宽着色）。但这超出了简单原始-对偶框架。为了符合题目要求，我们给出一个简单的原始-对偶 2-近似算法，假设图是树（或特殊图）。对于树，我们可以得到精确算法。但一般图，存在基于原始-对偶的 O(log n) 近似算法，其核心是构造对偶变量控制顶点间的“力”，类似于求解一个弹簧系统，使相邻顶点间的弹簧长度不超过 B，然后通过某种顺序分配整数位置。 第六步：算法实现与举例 考虑一个小例子：路径图 P₃：顶点 1-2-3，边 {1,2},{2,3}。我们希望最小带宽。显然最优排列是 1,2,3，带宽为 1。 二分搜索 B：设 B=1，我们需要找实数 p₁,p₂,p₃ 满足 |p₁-p₂|≤1, |p₂-p₃|≤1, 且都在 [ 1,3] 内。一个解：p₁=1, p₂=2, p₃=3，可行。所以 B* ≤1。 取实数解 p₁=1, p₂=2, p₃=3。 排序得 π(1)=1, π(2)=2, π(3)=3，带宽为 1，最优。 第七步：总结 图最小带宽排序问题可以通过线性规划松弛实数位置，然后舍入得到近似解。虽然一般图的近似比较难保证，但通过原始-对偶方法（对偶变量对应边约束的拉格朗日乘子）可以导出一个迭代调整顶点位置的算法。更复杂的算法可以获得 O(log n) 的近似比。在实际中，这种线性规划松弛提供了问题的下界，可用于分支定界精确求解。