英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
最大可满足问题的新3/4-近似算法
米歇尔X.古尔曼和大卫 P. 威廉姆森
摘要：Yannakakis最近提出一个最大可满足问题（MAX SAT）的3/4-近似算法。他的算法核心是以最大流量的解决问题。他提出的新的、简单的3/4-近似算法,应用概率统计方法和随机舍入解决最大可满足性问题的线性规划松弛。 结果表明,尽管标准随机舍入给不出一个好的近似结果,但是最佳的两个解决方案是随机取整和约翰逊的一个著名算法其最优解总是在3/4附近。这进一步表明，在随机舍入中一个不寻常的扭曲也会产生3/4-近似算法。作为分析的一个副产品，我们可以获得最差情况下线性规划松弛的相对偶间隙。
关键字：近似算法、最大可满足性、随机舍入,概率方法,性能保证,线性规划松弛
1. 简介：最大可满足问题(MAX SAT)的一个实例是由布尔子句的集合定义的，其中每个子句是析取于一组变量。一个子句是一个变量x或它的否定。另外，对于任意的子句,存在一个关联的非负权。最大可满足问题实例的最优解是一个真值分配给变量,最大化满足子句的权重之和(即子句中至少有一个文字为真)。MAX SAT被称为是NP完全问题，即使每个子句包含最多两个文本（有时也被称为MAX 2SAT）[4]。因此不太可能存在任何多项式时间算法使得MAX SAT存在最优解。
然而,许多人为最大可满足问题提出了alpha;-近似算法。对于MAX SAT的alpha;近似算法是一个多项式时间算法，即对于每一个实例，产生一个真值指派其权重至少是最优解权重的alpha;倍。约翰逊[7]证明了-近似算法，这也是一个-近似算法当每个子句包含至少k文字。特别是，当Kgt;2性能指标至少为。 Lieberherr 和Specker [9]给出了-近似算法(=0.618hellip;)当对于任意的该子句集不同时包含和。 Kohli 和 Krishnamurti [8] 提出一个随机算法，其所有方案中最优的预期权重至少为。Yannakakis最近改进了这些结果通过-近似算法[13]. Yannakakis的算法使MAX SAT实例转化成一个等效实例（在近似性方面），其不包含任何单元子句（即，子句只有一个文字）。与约翰逊的算法相结合，这保证了改进的性能保证。该算法采用一种简洁的方式最大流量计算来转换MAX 2SAT实例。然而，引入了一般性的子句时使转换变得更加复杂。
这篇文章的目的是提出新-近似算法，其对所有MAX SAT实例简单规范。这里提出的算法应用随机舍入（(Raghavan and Thompson [11], [10])）技术到一个单一的线性程序，他是最大可满足问题关于线性规划松弛的的解决方案。但是,一个简单的应用程序的技术不产生-近似算法。我们克服这个困难有两种方式：通过随机舍入与约翰逊的算法相结合，并使用标准随机舍入变化。
本文的结构如下。在2,综述了Johnson的算法的概率统计方法。在3, 我们表明,在最大可满足问题直接应用随机舍入线性规划松弛会导致-近似算法(=0.632hellip;)。在4中，对于给予的两种解决方案随机舍入和Johnson的算法，我们选择选择更好Johnson的算法由于其是一个-近似算法。在5中，我们描述了一类基于随机舍入的变体的最大可满足问题-近似算法。我们总结了几句话在6.
2. Johnson的算法和概率方法。假设我们独立随机地设置每个变量为真且概率。然后，通过这个概率分配满足子句的预期权重为
其中，（相应地，）表示集合的出现非否定的变量（相应地，否定）在。概率性方法指定必须存在一个真值指派，给变量的权重至少是这个期望值。事实上，可以应用条件概率的方法在多项式时间确定性找到这样的分配。在条件概率的方法中，对于给定的第个变量的值是在第次迭代确定, 通过计算概率分配满足子句的权重,并赋给且=1。然后计算预期权重赋予且=0. 变量被指定最大化条件期望的值。由于每个条件期望能够在多项式时间来计算，整体算法需要多项式时间，并如上断言，所产生的指派权重至少为.
Yannakakis解释[13]，约翰逊的算法的本质上是采用条件概率的方法对所有的建立。不难看出，这种选择的，
由于最佳指派权重至多为，这证明了约翰逊的算法是1 /2-近似算法。而且，如果所有的子句有至少个文字，然后
这意味着约翰逊的算法是-近似算法限制类的实例。
3. 一个-近似算法。考虑下面的整数规划：
基于:
联系=1 与集为真，=0 与集为假，=1与子句满足，=0与子句不满足，此整数规划（IP）正好对应于最大可满足问题，并且整数规划()的最优解正好等于MAX SAT问题的最优解。现在我们可以考虑整数线性规划松弛由约束条件代替且其。 称之为线性规划（LP）. 明显线性规划（LP）的最优值是整形规划（IP）的最优值的上界，即 。无论是否存在单元子句，对所有的()其解为=0.5(=1)在。这个值在内最佳，权独立。因此，该松弛是在这种情况下为空。然而,当有单位子句(约翰逊的算法的最坏情况),我们将在此,后来部分显示出这种放松提供了一些有用的信息。
我们现在表明，以简单的方式使用随机舍入，我们得到了最大可满足性问题的 -近似算法。该算法包括两个简单的步骤。第一步是解决线性规划（LP），让成为最优解。第二步是应用条件概率的方法对任意下得到一个指派。通过使用Tardos的算法[12]来解决线性规划（LP），该算法运行强多项式时间在线性规划约束矩阵所在项{-1,0,1}。
关于性能比的证明类似于2中记载的方法，虽然随机真值指派的预期权重比起更接近于。注意！如果
线性规划中对任意可行解和任意子句那么
这意味着所得的算法是一种-近似算法。
引理3.1。线性规划中对任意可行解和任意子句具有K文字，我们有
且
这和后来的证明用到了下面这个简单的结果。可见这个凹函数满足在区间,人们只需以显示它的间隔的端点，即 。我们还应当依靠算术几何平均不等式即
对于任何的非负集合。
证明。我们可以不失一般性的假设该子句中的所有变量被否定。确实，如果出现否定在子句，能替代的是他的否定在每个子句并且也可以用代替在不影响线性规划的可行性或在申索的引理说明。因此，我们认为该子句是及约束条件。我们需要证明
运用算术/几何平均不等式，并使用上的限制，我们得到
由于是一个凹函数，并且我们得出
证明所需的结果。
由于随着减少，引理3.1和前面的的讨论表明这个简单的算法是类可满足醒问题实例的一个-近似算法，最少有k个文字每个子句。另外由于，一般来说它是MAX 2SAT的一个-近似算法也是MAX SAT的一个-近似算法。
在一定意义上，我们刚刚进行的分析不能得到改善。考虑MAX SAT 实例组成的子句 （）权重为和 （）权重为1。我们可以知道在线性规划中唯一最优解是对于任意的，和
我们可以进一步研究
因此不等式是严谨的。然后，应用条件概率的方法来取得最优解，得到最佳真值指派。
4. 一个简单的-近似算法. 在2 ，我们知道了约翰逊算法是一个-近似算法其所有的子句至少包含两个文字，而在上一节，我们已经证明了-近似算法其所有的子句最多包含两个文字（即MAX 2SAT实例）。在这一节中，我们知道-近似算法可以通过选择两个真值指派输出在约翰逊的算法和前一节的算法之间获得。更正式地说，我们有以下结果。
引理4.1：对于所有的，的对应的预期权重为。对于所有的在，的对应的预期权重是是线性规划松弛下的一个最优解。那么
证明：第一个不等式明显是满足的。让表示子句集和确切的个文字。通过2，我们知道
当 。另一方面，引理3.1意味着
当
结果是
显然， 当。因此，
先前定理还表明，以下的算法是-近似算法：概率为，对于任意的设定概率的向量是或者并应用条件概率的方法。
5．一类-近似算法。在3中的标准的随机取整方法将直接导致-近似算法可以修改。为了这个目的，我们用（对任意的），让对那些恰当的函数并与之前一样应用条件概率的方法。下面讨论了可能的的选择。据我们所知，这是随机的舍入的第一个应用，其中所述概率不同于线性规划的解。
在3，如果我们能证明
对在线性规划中任意的可行解且对任意的子句，那么所得的算法是一个-近似算法。不等式(1)在上的共同约束条件激发了以下定。
定义5.1：函数具有属性如果
对任意的，和任意的。
截止在3的讨论中，任意的函数具有属性也包括-近似算法。下面的定理表明，该函数不仅存在固定属性并且具有选择灵活性。
定理5.2：任意函数满足
所有的有属性。
定理5.3：线性函数，当
有属性。
定理5.4：函数
具有属性。
对于可能的选择从定理5.2-5.4在图1中描绘。证明这些定理之前，我们希望能够就在这些定理条件下给出的函数属性说几句话。。
- 存在函数满足定理5.2的条件，由算术/几何平均不等式，即可得。
- 通过定理5.2,存在函数具有属性为此且。是这种情况，举个例子，属性且意味着随机舍入设置一个变量的值确定当。
-
对于且，注意任意的函数具有属性必须满足对所有的整数。这部分解释了选择的下界定理5.2。
上限考虑可以同样得到。 - 虽然不是一个具有固定属性的函数。但是存在线性函数有该属性如定理5。3所展示的那样。
- 定理5.3的线性函数对应的集合为真且起概率为。然而所得到的算法不同于定理4.1所提到的因为之间不是相互独立的。
- 定理5.4所描述的函数是“最接近“约翰逊的方式这这个意义上，对于任意的，定理5.4中的函数最大限度减少了在所有函数上的属性。确实，考虑到或，一个具有固定属性的派生函数满足(对任意的)。
我们的定理5.2-5.4使用类似的想法的证明，但定理5.4的证明是比别人多繁琐的，因为我们有几种情况需要区分。出于这个原因，我们省略其证明，但读者可以在本文中[6]的早期版本中找到它。为了证明定理，我们用下面的引理来限制我们重视的例子K（相当于子句没有否定变量）。
引理5.5 让称谓一个函数并满足
对所有的任意的。考虑任意函数满足
对所有的。那么具有属性。
证明：考虑到任意的且和任意的。那么
当()和()。
证明定理5.2引理5。5，我们只需要证明满足(2)。因此我们有
当.由于随着递增，为了证明(2)我们只需证明（对于任意。）这遵循凹函数，和。
定理5.3的证明。假设由于满足，为了使用引理5.5我们只需要证明满足(2)。我们可得
由算术/几何平均不等式。让，我们需要证明
对任意的。由于左侧随着递增，我们可以限制我们的重心在。此外，由于他在是凹的，我们只能确认(4)在 和 (该不等式是满足的)。对于这后面的变量，我们需要证明
对于任意的整数成立。当，不等式(5)成立直到到而(5)始终成立当。当，不等式(5)在
成立。我们可以证明是递减的在，因此不等式(6)恒有
6．结束语。具有属性的函数的存在证明了在线性规划下最差相对偶间隙，称之为。此外，这种最坏情况分析是严谨的，如从对MAX 2SAT实例可见
以单位权重。正如我们前面所观察到的，线性规划下的解（对所有的）和（对所有的）是最优的对任何没有单元子句的实例来说并且拥有变量。在这种情况下，ZP4，而。
我们的算法的性能保证也很严谨。对于任意没有单元子句的实例，我们所有的算法简化为约翰逊的算法，由于(对所有的)是线性规划下的最优解且上述所有的函数都有。在这个类实例下约翰逊的算法是一个近似算法，他给的这种类型的实例是严谨。此外，任何函数有属性必须满足。在此之前定义的属性的值，或并且。因此在不改变我们的分析或加强线性规划松弛，人们不能指望击败的性能保证。
阿罗拉等人[2]的结果暗示在MAX 2SAT和MAX 3SAT（每子句至多3文字）不能近似相当除非。由于本文的写作， MAX 3SAT最有名的常数是 [3]。这里还有很大空间可以丰富在这个结果和Yannakakis介绍的近似算法。
因此，它是一个有趣的悬而未决的
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29385]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
