技术摘要：预排序问题中的部分最优性

1. 问题陈述

预排序问题是一个定义在有限集 $V$ 上的组合优化任务，其中对于 $V^2$ 中的每一个有序对 $ab$（$a \neq b$），都关联有值$c_{ab} \in \mathbb{R}$。其目标是寻找$V$上的一个**预序**$\lesssim$（即一个自反且传递的二元关系），使得值之和$\sum_{a \lesssim b, a \neq b} c_{ab}$ 最大化。

该问题概括了聚类（其解为对称预序/等价关系）和偏序（其解为反对称预序）。预序的对称子集定义了一个聚类，而其反对称子集则定义了这些聚类之间的偏序。已知该问题是NP-hard的，即使当值被限制在 $\{-1, 1\}$ 时也是如此。

本文探讨了部分最优性问题：在不必要求解整个 NP-hard 实例的情况下，高效地判定对于一对子集 $ab$，在*每一个*最优预序中$a \lesssim b$或$a \not\lesssim b$ 是否成立。

2. 方法论

作者建立在改进映射（improving maps）框架之上，该技术由 Shekhovtsov (2013, 2014) 引入，并由 Shekhovtsov 等人 (2015) 应用。核心思想是构建从可行预序集到其自身的映射 $\sigma: X_V \to X_V$。如果一个映射是“改进的”（即它不会降低任何可行解的目标函数值），那么最优解就存在于该映射的像中。

该方法论分为三个阶段：

2.1 约束传播与部分刻画

作者定义了一个部分特征函数 $\tilde{x}$，它将值 $\{0, 1\}$ 分配给一对子集，而将 $\ast$（未决定）分配给其他对。他们引入了最大具体（maximally specific）部分函数的概念，其中所有由传递性约束强制为 0 或 1 的对都被明确决定。他们提供了一个高效算法来计算任意部分函数的闭包（$cl_V \tilde{x}$），确保所有隐含的约束都被传播。

2.2 部分最优性条件

本文推导了新的充分条件，在这些条件下，特定的对可以被固定为 0 或 1。这些条件通过构建特定的改进映射来验证：

• 割条件（定理 1 与推论 2）： 基于基本有向割映射（$\sigma_{\delta(U, V \setminus U)}$）。这些映射将跨越特定割 $(U, V \setminus U)$ 的所有边设为 0。定理 1 提供了一个涉及值 $c_{ij}$ 和割中正值之和的条件，以保证在最优解中 $x_{ij}=0$。推论 2 提供了一个更简单、可高效判定的特例。
• 并条件（定理 2）： 基于与有向割映射复合的基本并映射（$\sigma_{ij}$）。如果存在某些传递路径，这些映射会强制 $x_{ij}=1$。定理 2 建立了一个条件，其中设置 $x_{ij}=1$ 是最优的，这涉及比较 $c_{ij}$ 与特定路径集中负值之和。
• 固定条件（定理 3）： 一个更通用的条件，通过比较受限子空间上目标函数的下界和上界，将变量固定为 0 或 1。该定理涵盖了先前的条件（推论 4 和 5），并允许在特定局部界限和映射属性成立的情况下，即使全局界限不紧也能固定变量。

2.3 算法

作者提出了高效算法来应用这些条件：

• 割条件： 通过最小 $ij$-割问题（最大流）求解，具体使用推 - 重标算法（push-relabel algorithm）。
• 并条件： 表述为三标签能量最小化问题，使用$\alpha\beta$-交换移动（Boykov 等人，2001）启发式求解。
• 固定条件： 利用从局部搜索算法（贪婪弧固定/插入）和边不相交三元组打包中导出的近似界限来估计目标函数界限。在已知可行解 $x^+$ 的特定情况下，可以高效地计算紧界限。

3. 主要贡献

1. 新的部分最优性条件： 本文证明了新的条件（定理 1、2 和 3），这些条件概括并涵盖了 Böcker 等人 (2009) 和 Weller 等人 (2012) 的现有条件。
2. 高效验证算法： 作者提供了多项式时间算法来判定这些条件，利用了最大流、可达性分析和能量最小化启发式方法。
3. 约束传播框架： 对最大具体部分特征函数进行了严格定义，并提供了一个高效的闭包算法来传播约束。
4. 实证验证： 在合成数据和真实世界社交网络（Twitter 和 Google+）上进行了广泛实验。

4. 实验结果

算法在合成实例和真实社交网络自我网络（ego networks）上进行了评估。

• 合成数据：

  • 割条件： 定理 1 一致地将更多变量固定为零，比推论 2 多，但需要显著更多的计算时间（两个数量级）。
  • 并条件： 所有并条件均有效。推论 5（$b=1$）将最多的变量固定为 1。
  • 联合应用： 联合应用条件（割 + 并 + 固定）显著增加了固定变量的比例。对于“简单”实例（低噪声参数 $\alpha$），所有变量都被固定；对于“困难”实例，固定较少，但该比例仍高于先前方法。
  • 运行时间： 联合应用随顶点数 $|V|$ 呈多项式扩展（观察到的指数在 4.5 到 5.1 之间）。

• 真实世界数据（Twitter/Google+）：

  • 新条件（定理 1 和定理 3）将显著更多的变量固定为零，优于 Böcker 等人 (2009) 的最先进条件。
  • 具体而言，在 Twitter 数据上，定理 1 将中位数 29.6% 的变量固定为零，而推论 2 为 16.7%。
  • 虽然新条件的运行时间较长，但它仍然是多项式的，并且对于测试的数据集大小（$|V| \le 250$）是实用的。

5. 意义与主张

本文主张，所提出的条件和算法代表了部分解决预排序问题的最先进进展。

• 有效性： 主要贡献是提高了在最优预序中判定 $a \not\lesssim b$（将变量固定为 0）的能力。作者指出，虽然将变量固定为 1 的能力也有所提高，但最显著的增益在于识别非前驱关系。
• 通用性： 这些条件被证明是对先前工作的严格推广，能够在先前的条件（如推论 4 或 5）失效的情况下固定变量。
• 实用性： 这些方法在多项式时间内终止，并提供保证可扩展为最优解的部分解。这允许减少精确求解器的搜索空间，或为生物信息学和社会网络分析中的应用提供高质量的局部解。

作者保持了谦逊的语气，承认虽然这些条件提高了固定变量的比例，但该问题仍然是 NP-hard 的，并且这些算法旨在进行部分求解，而不是在所有情况下都精确求解整个实例。