A polynomial time approximation scheme for dense MIN 2SAT

被引：0
|
作者：
Bazgan, C
de la Vega, WF
机构：
[1] Univ Paris 11, LRI, F-91405 Orsay, France
[2] Univ Paris 11, CNRS, UMR 8623, LRI, F-91405 Orsay, France
来源：
FUNDAMENTALS OF COMPUTATION THEORY | 1999年 / 1684卷
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
It is proved that everywhere-dense MIN 2SAT and everywhere-dense MIN EQ both have polynomial time approximation schemes.
引用
收藏
页码：91 / 99
页数：9
相关论文
共 50 条
  • [11] Delaying Satisfiability for Random 2SAT
    Sinclair, Alistair
    Vilenchik, Dan
    APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES, 2010, 6302 : 710 - +
  • [12] Counting models for 2SAT and 3SAT formulae
    Dahllöf, V
    Jonsson, P
    Wahström, M
    THEORETICAL COMPUTER SCIENCE, 2005, 332 (1-3) : 265 - 291
  • [13] New Polynomial Classes for #2SAT Established Via Graph-Topological Structure
    De Ita, Guillermo
    Bello, Pedro
    Contreras, Meliza
    ENGINEERING LETTERS, 2007, 15 (02)
  • [14] Delaying Satisfiability for Random 2SAT
    Sinclair, Alistair
    Vilenchik, Dan
    RANDOM STRUCTURES & ALGORITHMS, 2013, 43 (02) : 251 - 263
  • [15] Compact linear programs for 2SAT
    Avis, David
    Tiwary, Hans Raj
    EUROPEAN JOURNAL OF COMBINATORICS, 2019, 80 : 17 - 22
  • [16] On determining the minimum length, tree-like resolution refutation of 2SAT, and extended 2SAT formulas
    Subramani, K
    ADVANCES IN COMPUTING SCIENCE-ASIAN 2002: INTERNET-COMPUTING AND MODELING, GRID COMPUTING, PEER-TO-PEER COMPUTING, AND CLUSTER COMPUTING, 2002, 2550 : 57 - 65
  • [17] Differential approximation of MIN SAT, MAX SAT and related problems
    Escoffier, Bruno
    Paschos, Vangelis Th.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 181 (02) : 620 - 633
  • [18] Differential approximation of MIN SAT, MAX SAT and related problems
    Escoffier, B
    Paschos, VT
    COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2005, VOL 4, PROCEEDINGS, 2005, 3483 : 192 - 201
  • [19] Improving nogood recording using 2SAT
    Stuckey, PJ
    Zheng, L
    15TH IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE, PROCEEDINGS, 2003, : 94 - 99
  • [20] A Linear Time Algorithm for Computing #2SAT for Outerplanar 2-CNF Formulas
    Lopez, Marco A.
    Raymundo Marcial-Romero, J.
    De Ita, Guillermo
    Moyao, Yolanda
    PATTERN RECOGNITION, 2018, 10880 : 72 - 81
12345