Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover
Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover
复制标题
最小 2SAT-DELETION：不近似性结果以及与最小顶点覆盖的关系
DOI：
10.1016/j.dam.2006.04.039
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
J. Chlebíková
中科院分区：
文献类型：
--
作者：
M. Chlebík;J. Chlebíková
MINIMUM 2SAT-DELETION 问题是删除 2SAT 实例中最小数量的子句以使其可满足。它是最小化问题的近似层次中的原型之一 Khanna 等人。 [约束满足：最小化问题的近似性，第 12 届 IEEE 计算复杂性年会论文集，德国乌尔姆，1997 年 6 月 24-27 日，第 282-296 页]，其近似性在很大程度上是开放的。我们证明了 85-15 ≈ 2.88854 的下近似界，改进了 Dinur 和 Safra 的先前界限 105-21 ≈ 1.36067 [有偏见的重要性，第 34 届 ACM 计算理论研讨会论文集 (STOC)，2002 年 5 月，第 33-42 页，还有 ECCC 报告 TR01-104， 2001]。对于每个变量恰好出现四次的高度受限实例，我们提供下限 32。两个不可近似性结果都适用于没有混合子句的实例（每个子句中的文字要么被否定，要么未被否定）。我们进一步证明，最小 2SAT-DELETION 问题的任何 k 近似算法多项式都可以简化为最小顶点覆盖问题的 (2-2/(k+1)) 近似算法。这些改进的一个组成部分是我们证明最小顶点覆盖问题最难在具有完美匹配的图上近似。更准确地说，为一般图多项式上的最小顶点覆盖设计 ρ 近似算法的问题在具有完美匹配的图上简化为相同的问题。这也改进了 Chen 和 Kanj 的结果 [关于具有完美匹配的图的近似最小顶点覆盖，第 11 届 ISAAC 会议记录，台北，台湾，计算机科学讲义，卷。 1969 年，施普林格，柏林，2000 年，第 132–143 页]。
The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems Khanna et al. [Constraint satisfaction: the approximability of minimization problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24–27 June, 1997, pp. 282–296], and its approximability is largely open. We prove a lower approximation bound of 85-15≈2.88854, improving the previous bound of 105-21≈1.36067 by Dinur and Safra [The importance of being biased, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), May 2002, pp. 33–42, also ECCC Report TR01-104, 2001]. For highly restricted instances with exactly four occurrences of every variable we provide a lower bound of 32. Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated). We further prove that any k-approximation algorithm for the MINIMUM 2SAT-DELETION problem polynomially reduces to a (2-2/(k+1))-approximation algorithm for the MINIMUM VERTEX COVER problem. One ingredient of these improvements is our proof that the MINIMUM VERTEX COVER problem is hardest to approximate on graphs with perfect matching. More precisely, the problem to design a ρ-approximation algorithm for the MINIMUM VERTEX COVER on general graphs polynomially reduces to the same problem on graphs with perfect matching. This improves also on the results by Chen and Kanj [On approximating minimum vertex cover for graphs with perfect matching, Proceedings of the 11st ISAAC, Taipei, Taiwan, Lecture Notes in Computer Science, vol. 1969, Springer, Berlin, 2000, pp. 132–143].
DOI：
--
发表时间：
2004
期刊：
Lecture Notes in Computer Science vol.3106
影响因子：
--
作者：
Tomokazu Imamura;Kazuo Iwama;Tatsuie Tsukiji
通讯作者：
Tatsuie Tsukiji