在线子模最大化与多路割问题的突破进展

### 在线子模最大化与多路割问题的突破进展 在算法领域，在线子模最大化和多路割问题一直是研究的热点。本文将深入探讨这两个问题的相关研究成果，包括在线子模最大化的近似比提升，以及多路割问题中积分间隙的改进。 #### 在线子模最大化：实现优于 1/2 的近似比 在线子模最大化旨在在满足一定约束条件下，最大化一个子模函数的值。为了证明定理 2 中给出的 19/33 界限，研究人员构建了一个分区拟阵和一个非负单调子模函数。 - **分区拟阵的构建**：分区拟阵的基集 N 由 32 个元素组成，分为四种类型： - \(o_1, o_2, o_3, o_4\) - \(x_1, x_2, x_3, x_4\) - \(y_{ij}\)，其中 \(i, j \in \{1, 2, 3, 4\}\) 且 \(i \neq j\) - \(z_{ijk}\)，其中 \(i, j, k \in \{1, 2, 3, 4\}\) 且 \(i, j, k\) 互不相同，同时忽略前两个索引的顺序（即 \(z_{ijk}\) 和 \(z_{jik}\) 表示同一个元素） 基集被划分为四个部分 \(P_1, P_2, P_3, P_4\)，每个部分 \(P_i\) 包含 8 个元素，形式为 \(o_i, x_i, y_{ji}, z_{jki}\)。 - **子模函数的定义**：子模函数 \(f\) 是一个加权覆盖函数，其定义的全集 U 由 28 个元素组成： \(U = \{a_i, b_i, c_i, d_i, e_i, f_i, g_i : i \in \{1, 2, 3, 4\}\}\) 元素的权重由函数 \(w: U \to R_{\geq 0}\) 给出，具体权重如下表所示： |元素| \(a_i\) | \(b_i\) | \(c_i\) | \(d_i\) | \(e_i\) | \(f_i\) | \(g_i\) | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | |权重 \(w(v)\) | 14 | 14 | 8 | 5 | 4 | 7 | 14 | 函数 \(f\) 的计算公式为 \(f(S) = w(\bigcup_{v \in S} v)\)，并且已知加权覆盖函数（权重非负）具有非负、单调和子模的性质。为了完整定义 \(f\)，还需要指定基集 N 中元素对应的集合： - \(o_i = \{a_i, b_i, c_i, d_i, e_i, f_i, g_i\}\) - \(x_i = \{b_j, c_j : j \neq i\}\) - \(y_{ij} = \{c_i, e_j\} \cup \{d_k, e_k, f_k : k \neq i, j\}\) - \(z_{ijk} = \{f_i, f_j, g_{\ell}\}\)，其中 \(\ell\) 是 \(\{1, 2, 3, 4\} \setminus \{i, j, k\}\) 中的唯一元素 - **近似比分析**：通过验证可知，该实例的最优解为 \(\{o_1, o_2, o_3, o_4\}\)，总权重为 264。而通过选择合适的破平规则，可以使算法 1 在处理部分 \(P_i, P_j, P_k, P_{\ell}\) 时，选择 \(x_i, y_{ij}, z_{ijk}, o_{\ell}\)，总权重为 152，从而得到近似比为 152/264 = 19/33。 #### 多路割问题：提升积分间隙下界 多路割问题是一个经典的组合优化问题，目标是将无向图的节点集划分为 k 个非空部分，每个部分包含一个终端节点，使得跨越划分的边的总权重最小。当 \(k \geq 3\) 时，该问题是 APX 困难的。 - **问题背景与现状**：目前已知的近似因子最好结果是 1.2965，而不可近似性结果表明，难以实现小于 1.2 的近似因子。研究人员通过构建 CKR 松弛的积分间隙实例，将下界提高到了 1.20016。 - **CKR 松弛**：CKR 松弛是一种线性规划松弛，从几何角度看待多路割问题。对于一个图 \(G = (V, E)\)，边权重为 \(w: E \to R_+\)，终端节点为 \(t_1, \ldots, t_k\)，CKR 松弛的表达式为： \[ \begin{align*} \min &\frac{1}{2} \