提升多路割问题的整性间隙

### 提升多路割问题的整性间隙 #### 1. 引言 在多路割问题中，找到合适的实例以提高整性间隙是一个重要的研究方向。本文将介绍一种通过凸组合构建的 4 路割实例，该实例在非对割情况下具有至少 1.20016 的间隙。 #### 2. 问题定义 考虑图 $G = (V, E)$，其中节点集 $V := \Delta_{4,n}$ 是离散化的 3 维单纯形，边集 $E_{4,n} := \{xy : x, y \in \Delta_{4,n}, \|x - y\|_1 = 2/n\}$。四个终端 $s_1, \ldots, s_4$ 是单纯形的四个顶点，即 $s_i = e_i$ ，$i \in [4]$。 割是一个函数 $P : V \to [5]$，满足 $P(s_i) = i$ ，$i \in [4]$。对应于 $P$ 的割集定义为 $\delta(P) := \{xy \in E_{4,n} : P(x) \neq P(y)\}$。对于节点集 $S$，$\delta(S)$ 表示恰好有一个端点在 $S$ 中的边集。给定权重函数 $w : E_{4,n} \to R^+$，割 $P$ 的成本为 $\sum_{e \in \delta(P)} w(e)$。 我们的目标是为边分配权重，使得得到的 4 路割实例在非对割情况下的间隙至少为 1.20016。 #### 3. 实例构建 我们的间隙实例是以下四个实例的凸组合： 1. **实例 $I_1$**：由 Angelidakis、Makarychev 和 Manurangsi 构造的 3 路割实例，间隙为 1.2 。为确保所有边的总权重恰好为 $n$，将其实例缩放为原来的 $6/5$，记为 $J$。在 $I_1$ 中，仅在面 $Face(s_1, s_2, s_3)$ 上使用实例 $J$，其余边的权重设为 0。 2. **实例 $I_2$**：将边集 $L_{12}, L_{23}, L_{13}$ 的权重设为 $1/3$，其余边的权重设为 0。 3. **实例 $I_3$**：将红色边的权重设为 $1/9c$，其余边的权重设为 0。 4. **实例 $I_4$**：将边集 $E_{4,n}$ 的权重设为 $1/n^2$。 对于乘数 $\lambda_1, \ldots, \lambda_4 \geq 0$，满足 $\sum_{i = 1}^4 \lambda_i = 1$，实例 $I$ 定义为 $I = \lambda_1I_1 + \lambda_2I_2 + \lambda_3I_3 + \lambda_4I_4$。每个实例中所有边的总权重为 $n + O(1)$，因此实例 $I$ 中所有边的总权重也为 $n + O(1)$。 #### 4. 凸组合的间隙 主要定理如下： **定理 3**：对于每个 $n \geq 10$ 和 $c \in (0, 1/2)$ ，使得 $cn$ 为整数，实例 $I$ 上的每个非对割的成本至少为以下两项的最小值： (i) $\lambda_2 + (1.2 - \frac{1}{n})\lambda_1 + \min_{\alpha \in [0, \frac{1}{2}]} \{0.4\alpha\lambda_1 + 3(\frac{1}{2} - \alpha)\lambda_4\}$ (ii) $2\lambda_2 + (1.2 - \frac{5}{2n})\lambda_1 + 3 \min \{ \frac{2\lambda_3}{9c}, \min_{\alpha \in [0, \frac{c^2}{2}]} \{0.4\alpha\lambda_1 + 3(\frac{c^2}{2} - \alpha)\lambda_4\}\}$ 从定理 3 可以得到以下推论： **推论 1**：存在常数 $c \in (0, 1/2)$ 和 $\lambda_1, \lambda_2, \lambda_3, \lambda_4 \geq 0$ ，满足 $\sum_{i = 1}^4 \lambda_i = 1$，使得实例 $I$ 中每个非对割的成本至少为 $1.20016 - O(1/n)$。具体设置为 $\lambda_1 = 0.751652$，$\lambda_2 = 0.147852$，$\lambda_3 = 0.000275$，$\lambda_4 = 0.100221$，$c = 0.074125$。 **定理 4**：对于每个常数 $c \in (0, 1/2)$ 和 $\lambda_1, \lambda_2, \lambda_3, \lambda_4 \geq 0$ ，满足 $\sum_{i = 1}^4 \lambda_i = 1$，存在一个非对割，其在实例 $I$ 中的成本至多为 $1.20067 + O(1/n)$。 #### 5. 定理 3 的证明 证明依赖于两个主要成分： 1. **引理 1**：设 $P$ 是 $\Delta_{4,n}$ 上的非对割，面 $Face(s_1, s_2, s_3)$ 中被标记为 1、2 或 3 的节点数为 $\alpha(n + 1)(n + 2)$ ，$\alpha \in [0, \frac{1}{2}]$ 。则 $|\delta(P)| \geq 3\alpha n(n + 1)$。 2. **Angelidakis、Makarychev 和 Manurangsi 构造的 3 路割实例的性质*