改进的MAXNAE-SAT和MAXSAT近似算法

# 改进的 MAX NAE - SAT 和 MAX SAT 近似算法 ## 1 RPR2 函数 为了获得更好的近似比，我们使用 RPR2 函数 f。对于不同的 f 选择，最小的 mink≥2 αk(f) 在两个 k 值（小于之前提到的 k0 参数）处取得，我们将这样的 k 值对应的最差 k - 配置称为最差配置。 之前的 MAX NAE - SAT 近似算法使用旋转角度 γ = 0.4555 的向外旋转，等价于使用函数 fγ(x) = Φ(x cot(0.4555)) 进行半定规划解的舍入。大量数值实验表明，对于任何旋转角度 γ 和任何 k ≥4，关于 fγ(x) = Φ(x cot γ) 的最差 k - 配置是 k/2 - 元组 (arccos(1 - 4/k), ..., arccos(1 - 4/k))。 在我们的算法中，使用分段线性 RPR2 函数 fNAE : R →[0, 1]，它连接点 (−∞, 0), (−3.9, 0), (−2.262, 0.044), (0, 0.044), (0, 0.956), (2.262, 0.956), (3.9, 1) 和 (∞, 1)，如图 1(a) 所示。 数值实验使我们认为，对于该函数，任何 k ≥4 的最差 k - 配置是满足 vi · vj = 1 - 4/k（1 ≤i < j ≤k）的配置。由此我们提出猜想： **猜想 1**：对于任何 k ≥4，ˆαk(fNAE) 的下确界在 1 ≤i < j ≤k 时，vi · vj = 1 - 4/k 时取得。 该猜想意味着对于所有 k ≥2，ˆαk(fNAE) > 0.8279。我们可以选择合适的参数 ε，使得 α(fNAE) > 0.8279。我们的算法在所有子句大小为 2 或 12 的实例上达到最坏情况比率。具体来说，对于最坏实例，半定规划的解 v1, ..., vn 满足对于每个子句 NAE(xi1, xi2)，vi1 · vi2 ≃−0.7638；对于每个子句 NAE(xi1, ..., xi12)，vil1 · vil2 = 1 - 4/12（1 ≤l1 < l2 ≤12）。 在寻找最优 RPR2 函数时，我们考虑了最多有八个转折点的各种分段线性对称单调 RPR2 函数。注意，使用的 fNAE 函数只有六个转折点。具有两个转折点的对称 RPR2 函数（通常称为 s - 线性 RPR2 函数）的近似比不如向外旋转。将 s - 线性 RPR2 函数与向外旋转相结合可以实现轻微改进。我们认为我们选择的 RPR2 函数接近最优。 ## 2 MAX SAT 近似算法 由于 MAX NAE - SAT 是 MAX SAT 的推广，我们目前的结果直接意味着一个推测近似比为 0.8279 的 MAX SAT 近似算法。下面介绍我们的 MAX SAT 近似算法。 ### 2.1 Asano 的 MAX SAT 近似算法 之前 Goemans 和 Williamson 将 MAX SAT 表述为以下整数规划（IP）问题： ```plaintext max ∑(j = 1 to m) wjzj s.t. zj ≤ ∑(l = 1 to kj) yil, Cj = xi1 ∨ xi2 ∨ ... ∨ xikj, 1 ≤ j ≤ m yi + yn + i = 1, 1 ≤ i ≤ n yi ∈ {0, 1}, 1 ≤ i ≤ 2n zj ∈ {0, 1}, 1 ≤ j ≤ m ``` 如果放松最后两个整数约束，允许变量 yi 和 zj 取 0 到 1 之间的任意值，就得到了 MAX SAT 的线性规划（LP）松弛。设 (y∗, z∗) 是 MAX SAT 的 LP 松弛的最优解。Goemans 和 Williamson 使用以下舍入方法：设 g : [0, 1] →[0, 1] 是一个舍入函数，对于 1 ≤i ≤n，以概率 g(y∗) 独立地将变量 xi 设置为 1。 Asano 提出了两类舍入函数： ```plaintext f a 3 (y) = { 1 - a / (4a^2)y, if y ∈ [0, 1/2] (4a^2)y / 4a, if y ∈ [1/2, 1] } f a 4 (y) = { ay + 1 - a, if y ∈ [0, 1 - ya] ay / 2 + 1/2 - a / 4, if y ∈ [1 - ya, ya] ay, if y ∈ [ya, 1] } where ya = 1/a - 1/2 ``` Asano 表明，使用舍入函数 f a 3 (y)（1/2 ≤a ≤√e/2 = 0.824360...），对于大小为 k 的子句，获得的近似比至少为： ```plaintext ζa k = { a, if k = 1 1 - 1 / (4a^(k - 2)), if k ≥ 2 } ``` 使用舍入函数 f a 4 (y)（√e/2 ≤a ≤1），对于大小为 k 的子句，获得的近似比至少为： ```plaintext ηa k = 1 - max { a^k (1 - 1/k)^k, a^(k - 2) / 4, a^k / 2 (1 - (1 - ya) / (k - 1))^(k - 1), 1 / (2k) (1 + a / 2 - a / k)^k }, for k ≥ 2 ηa k = a, for k = 1 ``` Asano 使用混合方法获得改进的 MAX SAT 近似算法，即并行运行多个算法并返回具有最大值的解。具体来说，该算法首先求解一个包含之前算法中所有松弛（LP 和 SDP）的 MAX SAT 半定规划松弛。如果使用 Goemans 和 Williamson 的舍入过程，分别结合舍入函数 f a 3、Feige 和 Goemans 的 MAX 2 - SAT 舍入过程以及 Halperin 和 Zwick 的 MAX 3 - SAT 舍入过程，可获得 0.7877 的性能保证；如果结合舍入函数 f a 4 和 [Zwi99] 的 MAX NAE - SAT 舍入过程，可获得推测的 0.8353 的性能保证。 ### 2.2 MAX SAT 的半定规划松弛 MAX SAT 的半定规划松弛如下： ```plaintext Max ∑(j = 1 to m) wjzj s.t. zj ≤ ∑(l = 1 to kj) yil zj ≤ (1 / (kj - 1)) ∑(1 ≤ p < q ≤ kj) (3 - v0 · vip - v0 · viq，vip · viq) / 4, kj ≥ 2 zj ≤ (1 / (kj - 1 choose 2)) ∑(1 ≤ l1 < l2 < l3 ≤ kj) uil1 il2 il3, kj ≥ 3 zj ≤ (kj + 1 - ∑(l = 0 to ```