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 条
  • [1] Approximating a generalization of MAX 2SAT and MIN 2SAT
    Hochbaum, DS
    Pathria, A
    DISCRETE APPLIED MATHEMATICS, 2000, 107 (1-3) : 41 - 59
  • [2] A Threshold for a Polynomial Solution of #2SAT
    De Ita, Guillermo
    Raymundo Marcial-Romero, J.
    Antonio Hernandez, Jose
    FUNDAMENTA INFORMATICAE, 2011, 113 (01) : 63 - 77
  • [3] A Parametric Polynomial Deterministic Algorithm for #2SAT
    Raymundo Marcial-Romero, J.
    De Ita Luna, Guillermo
    Antonio Hernandez, J.
    Maria Valdovinos, Rosa
    ADVANCES IN ARTIFICIAL INTELLIGENCE AND SOFT COMPUTING, MICAI 2015, PT I, 2015, 9413 : 202 - 213
  • [4] Simple Approximation Algorithms for Balanced MAX 2SAT
    Paul, Alice
    Poloczek, Matthias
    Williamson, David P.
    ALGORITHMICA, 2018, 80 (03) : 995 - 1012
  • [5] Simple Approximation Algorithms for Balanced MAX 2SAT
    Alice Paul
    Matthias Poloczek
    David P. Williamson
    Algorithmica, 2018, 80 : 995 - 1012
  • [6] New approximation algorithms for MAX 2SAT and MAX DICUT
    Matuura, S
    Matsui, T
    JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 2003, 46 (02) : 178 - 188
  • [7] Efficient Polynomial-Time Approximation Scheme for the Genus of Dense Graphs
    Jing, Yifan
    Mohar, Bojan
    2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2018, : 719 - 730
  • [8] Linear-Time Algorithm for Quantum 2SAT
    Arad, Itai
    Santha, Miklos
    Sundaram, Aarthi
    Zhang, Shengyu
    THEORY OF COMPUTING, 2018, 14 : 1 - 27
  • [9] Efficient polynomial-time approximation scheme for the genus of dense graphs
    Jing, Yifan
    Mohar, Bojan
    JOURNAL OF THE ACM, 2024, 71 (06)
  • [10] MAX SAT approximation beyond the limits of polynomial-time approximation
    Dantsin, E
    Gavrilovich, M
    Hirsch, EA
    Konev, B
    ANNALS OF PURE AND APPLIED LOGIC, 2002, 113 (1-3) : 81 - 94
12345