打破对称性以拯救平方和：最小完工时间调度问题研究

### 打破对称性以拯救平方和：最小完工时间调度问题研究 #### 1. 引言 在组合优化领域，提升 - 投影层次结构（如 Sherali & Adams (SA)、Lovász & Schrijver (LS) 或平方和 (SoS)）是获取一系列越来越紧密松弛的系统方法。然而，对于哪些问题这些层次结构能产生与最佳近似算法匹配的松弛，目前尚未完全明确。许多用于获得下界的实例具有高度对称的结构，这暗示了这些层次结构所提供的松弛的紧密性与对称性之间存在紧密联系。 本文聚焦于一个特定的相关问题——相同机器上的最小完工时间调度问题。该问题的输入包括一组 $n$ 个作业的集合 $J$，每个作业有一个正整数处理时间 $p_j > 0$，以及一组 $m$ 台相同机器的集合 $M = [m]$。目标是找到一种作业到机器的分配方案，使最大负载（即完工时间）最小化。此问题是强 NP 难问题，但存在基于不同技术（如动态规划和整数规划的某些可处理版本）的多项式时间近似方案。 该问题有两种自然的线性松弛： - **分配线性规划**：使用二进制变量 $x_{ij}$ 表示作业 $j$ 是否分配给机器 $i$，其整数间隙为 2。 - **配置线性规划**：使用指数数量的变量 $y_{iC}$ 表示分配给机器 $i$ 的作业集的处理时间多重集是否为 $C$。Kurpisz 等人表明，即使经过 LS + 或 SA 层次结构的线性轮数，配置线性规划的整数间隙至少为 $1024/1023 ≈ 1.0009$。 #### 2. 研究动机与目标 本文旨在研究问题表述中的对称性如何降低 SoS 层次结构所获得的松弛的性能。具体目标如下： - 确定 SoS 层次结构应用于配置线性规划时，经过常数轮数是否能达到 $(1 + ε)$ 的整数间隙。 - 探索对称处理技术是否能克服 SoS 层次结构在某些调度实例中的局限性。 #### 3. 相关工作综述 - **上界结果** - Goemans 和 Williamson 将半定规划应用于最大割问题。 - Karlin 等人基于 SoS 为最大背包问题设计了近似方案。 - Levey 和 Rothvoss 为固定数量的机器设计了 SA 层次结构下的近似方案。 - SoS 方法在矩阵和张量完成、张量分解和聚类等问题中得到应用。 - **下界结果** - Grigoriev 表明 refute 一个简单的背包实例需要线性数量的 SoS 轮数。 - Laurent 为最大割问题和 Kurpisz 等人针对无约束多项式优化问题得到了类似结果。 - Grigoriev 和 Schoenebeck 展示了 SoS 在子指数时间内证明随机 3 - SAT 实例不可满足性的困难。 - **不变平方和** - Gatermann 和 Parrillo 研究了在多项式不变于群作用时如何获得简化的平方和非负性证明。 - Raymond 等人扩展了该方法以构造 k - 子集超立方体上多项式的对称简化平方和证明。 - **整数规划中的对称性处理** - 整数规划社区通过打破对称性或设计对称感知的精确算法来处理对称性。 - Ostrowski 使用 SA 层次结构降低提升松弛的维度以获得更快的算法。 #### 4. 预备知识：平方和与伪期望 - **多项式环与商环**：用 $R[x]$ 表示实系数多项式环。对于给定的索引集 $M$、$J$ 和 $E$，考虑集合 $K$： \[ K = \left\{x \in R^E : g_i(x) \geq 0 \ \forall i \in M, h_j(x) = 0 \ \forall j \in J, x_e^2 - x_e = 0 \ \forall e \in E\right\} \] 其中 $g_i, h_j \in R[x]$。用 $I_E$ 表示由 $\{x_e^2 - x_e : e \in E\}$ 生成的多项式理想，$R[x]/I_E$ 表示在理想 $I_E$ 中消失的多项式的商环。 - **平方和多项式**：如果存在商环中的有限多项式族 $\{s_{\alpha}\}_{\alpha \in A}$，使得 $f \equiv \sum_{\alpha \in A} s_{\alpha}^2 \mod I_E$，则称多项式 $f \in R[x]/I_E$ 为平方和多项式（SoS）。 - **证书与 SoS 方法**：如果存在 SoS 多项式 $s_0$ 和 $\{s_i\}_{i \in M}$，以及多项式 $\{r_j\}_{j \in