MAX-3SAT

(Updated: )

随机算法的近似比

如果问题的最优解为 , 随机算法的期望解为 , 并且期望满足 , 就说随机算法的近似比是

这个 是期望值, 并不代表最坏情况

MAX-E3SAT

假设子句个数为 , 变量数量为 , 并且每个子句中恰好有 个变量 (Exact 3SAT)

每次按 概率随机选取某个变量的取值为

那么这个随机算法的近似比是

这也简单, 因为每个子句满足的概率是

所以期望有 个子句满足

为了说明这个界是紧的, 给一个例子:

即 重复出现两次, 有一个或两个反的子句各出现一次

那么期望 个子句被满足, 而最优解为

所以近似比是

MAX-3SAT

近似比 8/7 的算法

使用半正定松弛 (SDR) 的方法, 将 MAX-3SAT 问题转化成半正定规划 (SDP) 问题

(SDR = semidefinite relaxation, SDP = semidefinite programming)

假设一共 个变量 , 满足

MAX-3SAT 的权值为

那么我们要求

将每个变量 转化成一个 维单位向量 , 其中 用于表示

所以

其中

并且对于 , 我们转化成

并且我们令标量 表示子句 的值

那么我们通过规划 以及 的取值, 就可以得到最优解

所以问题转化成了 SDP 问题:

alt text

我们记

定义一个松弛量:

于是约束就是

不妨设

这种情况下可以计算得出

alt text

即存在一个向量组 与 MAX-3SAT 中的任意一种分配 对应

所以我们使用 SDP 优化得到的目标最大值就对应着 MAX-3SAT 的最大值

但这种向量组不止一种: 任取 , 只要 时 , 时 , 这样的向量组就满足上面的等式

那么如果 并不是某个平行于坐标轴的向量, 我们如何将 转化回 ?

我们可以用一个任取的, 过原点的超平面来分割 与其他向量

如果某个 与 处于超平面的两侧, 那么 ; 否则

近似比分析

长度为 1 的子句 (MAX-CUT)

对于长度为 的子句, 我们令 , 得出

这个式子恰好是 MAX-CUT 对应的松弛方法

对于两个向量 , 我们用一个随机的超平面将他们分割的概率为 , 其中 为 与 的夹角

并且

所以对于某个子句 , 有如下不等式:

长度为 2 的子句 (MAX-2SAT)

对于长度为 的子句, 我们令 , 得出

这个式子类似于 MAX-2SAT 对应的松弛方法

  • 对于上面定义 维向量是因为一共有 个变量, 为了让不同向量之间是正交的
  • 例如, 如果 MAX-3SAT 中只有 个变量, 我们可以定义 , 不需要更多维数了

证明近似比是最优的

Hastad

一个 gadget 是一个有限的组合结构, 将一个问题的

Random MAX-3SAT

近似比 9/8 的算法

参考:

  1. A 7/8-Approximation Algorithm for MAX 3SAT?
  2. 9/8-Approximation Algorithm for Random MAX-3SAT
  3. Some Optimal Inapproximability Results
  4. Gadgets, Approximation, and Linear Programming
  5. 算法导论