Approximating MIN 2-SAT and MIN 3-SAT

被引：0
|
作者：
Adi Avidor
Uri Zwick
机构：
[1] School of Computer Science,
[2] Tel-Aviv University,undefined
[3] Tel-Aviv 69978,undefined
来源：
Theory of Computing Systems | 2005年 / 38卷
关键词：
Computational Mathematic; Approximation Algorithm; Approximation Result; Improve Approximation Algorithm; Obtain Approximation Algorithm;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We obtain substantially improved approximation algorithms for the MIN k-SAT problem, for k = 2,3. More specifically, we obtain a 1.1037-approximation algorithm for the MIN 2-SAT problem, improving a previous 1.5-approximation algorithm, and a 1.2136-approximation algorithm for the MIN 3-SAT problem, improving a previous 1.75-approximation algorithm for the problem. These results are obtained by adapting techniques that were previously used to obtain approximation algorithms for the MAX k-SAT problem. We also obtain some hardness of approximation results.
引用
收藏
页码：329 / 345
页数：16
相关论文
共 50 条
  • [21] Randomized algorithms for 3-SAT
    Hofmeister, Thomas
    Schoening, Uwe
    Schuler, Rainer
    Watanabe, Osamu
    THEORY OF COMPUTING SYSTEMS, 2007, 40 (03) : 249 - 262
  • [22] Research on the Solution Space of 2-SAT and Max-2-SAT
    Li, Bai-Feng
    Wei-Wei
    Liu, Chao-Qun
    3RD ANNUAL INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY AND APPLICATIONS (ITA 2016), 2016, 7
  • [23] Placing quantified variants of 3-SAT and NOT-ALL-EQUAL 3-SAT in the polynomial hierarchy
    Doecker, Janosch
    Dorn, Britta
    Linz, Simone
    Semple, Charles
    THEORETICAL COMPUTER SCIENCE, 2020, 822 : 72 - 91
  • [24] The phase transition in 1-in-k SAT and NAE 3-SAT
    Achlioptas, D
    Chtcherba, A
    Istrate, G
    Moore, C
    PROCEEDINGS OF THE TWELFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2001, : 721 - 722
  • [25] The scaling window of the 2-SAT transition
    Bollobás, B
    Borgs, C
    Chayes, JT
    Kim, JH
    Wilson, DB
    RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) : 201 - 256
  • [26] Random 2-SAT: results and problems
    de la Vega, WF
    THEORETICAL COMPUTER SCIENCE, 2001, 265 (1-2) : 131 - 146
  • [27] FPGA based accelerator for 3-SAT conflict analysis in SAT solvers
    Safar, M
    El-Kharashi, MW
    Salem, A
    CORRECT HARDWARE DESIGN AND VERIFICATION METHODS, PROCEEDINGS, 2005, 3725 : 384 - 387
  • [28] 3-SAT EQUALS SAT FOR A CLASS OF NORMAL MODAL-LOGICS
    DEMRI, S
    INFORMATION PROCESSING LETTERS, 1995, 54 (05) : 281 - 287
  • [29] Random 3-SAT: The Plot Thickens
    Cristian Coarfa
    Demetrios D. Demopoulos
    Alfonso San Miguel Aguirre
    Devika Subramanian
    Moshe Y. Vardi
    Constraints, 2003, 8 : 243 - 261
  • [30] Improved Randomized Algorithms for 3-SAT
    Iwama, Kazuo
    Seto, Kazuhisa
    Takai, Tadashi
    Tamaki, Suguru
    ALGORITHMS AND COMPUTATION, PT I, 2010, 6506 : 73 - +
12345